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

Abstract

We first motivate and define a notion of asymptoticdifferential approximation ratio. For this, we introduce a new class ofproblems called radial problems including in particular the hereditaryones. Next, we validate the definition of the asymptotic differentialapproximation ratio by proving positive, conditional and negativeapproximation results for some combinatorial problems. We first derive adifferential approximation analysis of a classical greedy algorithm forbin packing, the “first fit decreasing”. Next we deal with minimumvertex-covering-by-cliques of a graph and the minimumedge-covering-by-complete-bipartite-subgraphs of a bipartite graph anddevise a differential-approximation preserving reduction from the formerto the latter. Finally, we prove two negative differential approximationresults about the ability of minimum vertex-coloring to be approximatedby a polynomial time approximation schema.