Completeness in differential approximation

Giorgio Ausiello*, Università degli Studi di Roma
Cristina Bazgan**, LAMSADE
Marc Demange, ESSEC - Department of Decision and Information Systems et CERMSEM
Vangelis Th. Paschos**, LAMSADE

Résumé. Nous étudions la question de complétude pour les classes d'approximation différentielle. Dans le cadre de l'approximation différentielle, la qualité d'un algorithme d'approximation compare la valeur approchée à la pire valeur de l'instance et à sa valeur optimale. Les classes les plus souvent utilisées sont DAPX, la version différentielle de APX, qui contient les problèmes d'optimisation de NP approximables en temps polynomial avec un rapport d'approximation différentiel constant et DGLO, la version différentielle de GLO, formée des problèmes pour lesquels un optimum local garantit un rapport d'approximation différentiel constant. Nous définissons des réductions préservant l'approximation naturelles dans ce cadre et établissons des résultats de complétude pour la classe NPO des problèmes d'optimisation de NP ainsi que pour DAPX et pour une sous-classe naturelle de DGLO. Nous introduisons aussi la classe O-APX des problèmes de NPO qui n'admettent, sous l'hypothèse P différent de NP, aucun rapport différentiel strictement supérieur à 0. Cette classe est très naturelle dans le cadre différentiel alors qu'elle n'a pas de sens dans le cadre classique. Pour 0-APX, nous établissons des résultats de complétude par rapport à des réductions appropriées. Enfin, nous prouvons l'existence de problèmes difficiles pour DPTAS, la classe des problèmes de NPO qui admettent un schéma différentiel d'approximation polynomiale.
Mots-clés : Approximation différentielle, réductions préservant l'approximation, complétude en approximation.

Abstract. We study completeness in differential approximability classes. In differential approximation, the quality of an approximation algorithm is the measure of both how far is the solution computed from a worst one and how close is it to an optimal one. The classes mainly considered are DAPX, the differential counterpart of APX, including the NP optimization problems approximable in polynomial time within constant differential approximation ratio and the DGLO, the differential counterpart of GLO, including problems for which their local optima guarantee constant differential approximation ratio. We define natural approximation preserving reductions and prove completeness results for the class of the NP optimization problems (class NPO), as well as for DAPX and for a natural subclass of DGLO. We also define class 0-APX of the NPO problems that are not differentially approximable within any ratio strictly greater than 0 unless P = NP. This class is very natural for differential approximation, althrough has no sens for the standard one. For 0-APX also we prove completeness results under a suitably defined reduction. Finally, we prove the existence of hard problems for DPTAS, the class of NPO problems solvable by polynomial time differential approximation schemata.
Keywords : Differential approximation, reductions preserving approximation, completness in approximation classes.

AMS Classification : 03D15, 68Q25, 68R05.

*Dipartimento di Informatica e Sistemistica, Università degli Studi di Roma "La Sapienza", via salaria 113, 00198, Roma, Italy.
**LAMSADE, Université Paris-Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France.