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

Issue		RAIRO Oper. Res. Volume 33, Number 4, October-December 1999


Page(s)		481 - 507
DOI		10.1051/ro:1999121

DOI: 10.1051/ro:1999121

RAIRO Rech. Opér. (vol. 33, n $^\circ$ 1, 1999, pp. 481-507)

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

Marc Demange¹ and Vangelis Th. Paschos²

¹CERMSEM, Universite Paris I, 106-112 boulevard de l'Hôpital, 75647 Paris Cedex 13, France.
²LAMSADE, Universite Paris-Dauphine, Place du Marechal de Lattre de Tassigny, 75775 Paris Cedex 16, France.

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.

Résumé:

Nous commençons par définir et motiver une notion de rapport d'approximation différentiel asymptotique. Pour cela, nous introduisons une classe de problèmes que nous appelons radiaux qui comprend en particulier les problèmes héréditaires. Puis nous validons la définition de rapport d'approximation différentiel asymptotique en établissant des résultats positifs, conditionnels et négatifs pour différents problèmes combinatoires. Nous proposons d'abord une analyse, dans le cadre de l'approximation différentielle, d'un algorithme glouton classique (le first fit decreasing ) pour le problème de bin packing. Nous traitons alors les problèmes de couverture minimum des sommets d'un graphe par des cliques induites et des arêtes d'un graphe biparti par des sous-graphes partiels bipartis complets et donnons une réduction préservant l'approximation différentielle du premier au second. Enfin, nous prouvons deux résultats négatifs concernant la possibilité d'approcher le problème de coloration des sommets d'un graphe par un schéma d'approximation différentiel polynomial.

Keywords: NP-complete problem, complexity, polynomial time approximation algorithm, bin packing, coloring, covering.

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.