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

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

0.00 Avg rating0 Votes
Article ID: iaor20052849
Country: France
Volume: 33
Issue: 4
Start Page Number: 481
End Page Number: 507
Publication Date: Oct 1999
Journal: RAIRO Operations Research
Authors: ,
Keywords: bin packing
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.