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

Demange, Marc, and Paschos, Vangelis Th.. "Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems." RAIRO - Operations Research 33.4 (2010): 481-507. <http://eudml.org/doc/197785>.

@article{Demange2010,
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. },
author = {Demange, Marc, Paschos, Vangelis Th.},
journal = {RAIRO - Operations Research},
keywords = { NP-complete problem; complexity; polynomial time approximation algorithm; bin packing; coloring; covering. ; NP-complete problem; polynomial time approximation algorithm; covering},
language = {eng},
month = {3},
number = {4},
pages = {481-507},
publisher = {EDP Sciences},
title = {Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems},
url = {http://eudml.org/doc/197785},
volume = {33},
year = {2010},
}

TY - JOUR
AU - Demange, Marc
AU - Paschos, Vangelis Th.
TI - Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 4
SP - 481
EP - 507
AB - 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.
LA - eng
KW - NP-complete problem; complexity; polynomial time approximation algorithm; bin packing; coloring; covering. ; NP-complete problem; polynomial time approximation algorithm; covering
UR - http://eudml.org/doc/197785
ER -