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

Marc Demange; Vangelis Th. Paschos

RAIRO - Operations Research (2010)

- Volume: 33, Issue: 4, page 481-507
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topDemange, 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.