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

We first motivate and define a notion of asymptotic differential approximation ratio. For this, we introduce a new class of problems called radial problems including in particular the hereditary ones. Next, we validate the definition of the asymptotic differential approximation ratio by proving positive, conditional and negative approximation results for some combinatorial problems. We first derive a differential approximation analysis of a classical greedy algorithm for bin packing, the ‘first fit decreasing’. Next we deal with minimum vertex-covering-by-cliques of a graph and the minimum edge-covering-by-complete-bipartite-subgraphs of a bipartite graph and devise a differential-approximation preserving reduction from the former to the latter. Finally, we prove two negative differential approximation results about the ability of minimum vertex-coloring to be approximated by a polynomial time approximation schema.