Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems

We first motivate and define a notion of asymptotic differential approximat ion mTio. For this, we introduce a new class of problems called radial prob lems including in particular the hereditary ones. Next, we validate rile de finition of rile asymptotic differential approximation ratio by proving pos itive, conditional and negative approximation results for some combinatoria l problems. We first derive a differential approximation analysis of a clas sical greedy algorithm for bin packing, rile "first fit decreasing". Next w e deal with minimum vertex-covering-by-cliques of a graph and rile minimum edge-covering-by-complete-bipartite-subgraphs of bipartite graph and devise a differential-approximation preserving reduction from the former to the l atter. Finally, we prove two negative differential approximation results ab out the ability of minimum vertex-coloring to be approximated by a polynomi al time approximation schema.