Dureté d'approximation - erreur additive

Il existe une littérature abondante et au moins un très bon livre exposant la dureté connue des résultats d'approximation pour les problèmes NP-difficiles dans le contexte d'erreur multiplicative (par exemple, l'approximation 2 pour la couverture des sommets est optimale en supposant UGC). Cela inclut également des classes de complexité d'approximation bien comprises telles que APX, PTAS, etc.

Que sait-on quand une erreur additive doit être prise en compte? Une recherche documentaire montre quelques résultats de type borne supérieure, notamment pour le regroupement de casiers (voir par exemple http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps ), mais existe-t-il une classification de classe de complexité plus complète ou y a-t-il une raison pour laquelle elle n'est pas si intéressante ou pertinente?

En guise de commentaire supplémentaire, pour le casier d'emballage, par exemple, il n'y a pour autant que je sache aucune raison théorique pour laquelle un algorithme de temps poly qui est toujours à une distance additive de l'optimal de 1 n'a pas pu être trouvé (bien que je sois corrigé ). Un tel algorithme réduirait-il des classes de complexité ou aurait-il un autre effet d'entraînement théorique significatif?

EDIT: La phrase clé que je n'ai pas utilisée est "classe d'approximation asymptotique" (merci Oleksandr). Il semble qu'il y ait du travail dans ce domaine mais il n'a pas encore atteint le même stade de maturité que la théorie des classes d'approximation classiques.

La question est quelque peu ouverte, je ne pense donc pas pouvoir y répondre complètement. Ceci est une réponse partielle.

Une observation facile est que de nombreux problèmes sont sans intérêt lorsque l'on considère l'approximation additive. Par exemple, traditionnellement, la fonction objective du problème Max-3SAT est le nombre de clauses satisfaites. Dans cette formulation, approximer Max-3SAT dans une erreur additive O (1) équivaut à résoudre Max-3SAT exactement, simplement parce que la fonction objectif peut être mise à l'échelle en copiant plusieurs fois la formule d'entrée. Une approximation multiplicative est beaucoup plus essentielle pour les problèmes de ce type.

[Edit: Dans la révision précédente, j'avais utilisé le jeu indépendant comme exemple dans le paragraphe précédent, mais je l'ai changé en Max-3SAT parce que le jeu indépendant n'est pas un bon exemple pour illustrer la différence entre approximation multiplicative et approximation additive; approximer l'ensemble indépendant même dans un facteur multiplicatif O (1) est également NP-difficile. En fait, une inapproximabilité beaucoup plus forte pour l'ensemble indépendant est montrée par Håstad [Has99].]

Mais, comme vous l'avez dit, l'approximation additive est intéressante pour les problèmes comme le bin bining, où nous ne pouvons pas mettre à l'échelle la fonction objectif. De plus, on peut souvent reformuler un problème afin que l'approximation additive devienne intéressante.

Par exemple, si la fonction objective de Max-3SAT est redéfinie comme le rapport du nombre de clauses satisfaites au nombre total de clauses (comme cela est parfois fait), l'approximation additive devient intéressante. Dans ce cadre, l'approximation additive n'est pas plus difficile que l'approximation multiplicative dans le sens où l'approximation à l'intérieur d'un facteur multiplicatif 1− ε (0 < ε <1) implique l'approximation à l'intérieur d'une erreur additive ε , car la valeur optimale est toujours au plus 1.

Un fait intéressant (qui semble malheureusement souvent ignoré) est que de nombreux résultats d'inapproximabilité prouvent l'exhaustivité NP de certains problèmes d'écart.qui ne résulte pas de la simple dureté NP de l'approximation multiplicative (voir aussi Petrank [Pet94] et Goldreich [Gol05, section 3]). Poursuivant l'exemple de Max-3SAT, c'est un résultat bien connu de Håstad [Has01] qu'il est difficile NP d'approximer Max-3SAT dans un facteur multiplicatif constant meilleur que 7/8. Ce résultat à lui seul ne semble pas impliquer qu'il est difficile pour NP d'approcher la version de ratio de Max-3SAT dans une erreur additive constante au-delà d'un certain seuil. Cependant, ce que prouve Håstad [Has01] est plus fort que la simple inapproximabilité multiplicative: il prouve que le problème de promesse suivant est NP-complet pour chaque constante 7/8 < s <1:

Gap-3SAT _de
l' instance : Une formule CNF de φ où chaque clause implique exactement trois variables distinctes.
Oui-promesse : φ est satisfaisable.
Pas de promesse : aucune assignation de vérité ne satisfait plus que la fraction s des clauses de φ.

De cela, nous pouvons conclure qu'il est difficile de NP approximer la version de rapport de Max-3SAT dans une erreur additive meilleure que 1/8. En revanche, l'assignation aléatoire simple et habituelle donne une approximation au sein d'une erreur additive 1/8. Par conséquent, le résultat de Håstad [Has01] ne donne pas seulement l'inapproximabilité multiplicative optimale pour ce problème mais aussi l'inapproximabilité additive optimale. Je suppose qu'il existe de nombreux résultats d'inapproximabilité additifs comme celui-ci qui n'apparaissent pas explicitement dans la littérature.

Les références

[Gol05] Odre Goldreich. Sur les problèmes de promesse (enquête à la mémoire de Shimon Even [1935-2004]). Colloque électronique sur la complexité informatique , rapport TR05-018, février 2005. http://eccc.hpi-web.de/report/2005/018/

[Has99] Johan Håstad. La clique est difficile à approximer dans n ^{1− ε} . Acta Mathematica , 182 (1): 105–142, mars 1999. http://www.springerlink.com/content/m68h3576646ll648/

[Has01] Johan Håstad. Quelques résultats d'inapproximabilité optimaux. Journal de l'ACM , 48 (4): 798–859, juillet 2001. http://doi.acm.org/10.1145/502090.502098

[Pet94] Erez Petrank. La dureté de l'approximation: l'emplacement de l'écart. Complexité informatique , 4 (2): 133-157, avril 1994. http://dx.doi.org/10.1007/BF01202286

Ceci est une réponse partielle

$ABS$$ABS$

$NP$

-Chaque graphique cubique est à 4 couleurs à colorier en temps polynomial, mais la couleur à 3 couleurs est dure NP.

$ABS$$P=NP$

Il existe un travail récent sur les classes d'approximation asymptotiques et leur comparaison avec leurs homologues classiques.

Erik Jan van Leeuwen et Jan van Leeuwen. Structure de l'approximation polynomiale du temps . Rapport technique UU-CS-2009-034. Décembre 2009.