Dureté d'approximation - erreur additive

24

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.

Raphael
la source
Quel est le titre du livre que vous mentionnez?
Karolina Sołtys
2
Je ne suis pas sûr que ce soit vrai. Voir la page 2 des notes liées dans la question, en particulier les théorèmes 3 et 4 et le problème ouvert énoncé juste en dessous du théorème 4. Le livre auquel je faisais référence était Algorithmes d'approximation de Vijay Vazirani, ce qui est excellent.
Raphael
Frieze et Kannan ( research.microsoft.com/en-us/um/people/kannan/Papers/… ) ont donné un algorithme aléatoire à temps constant avec l'erreur additive epsilon n ^ k pour tout problème de satisfaction de contrainte max avec des contraintes d'arity k.
Warren Schudy
Je pense que le regroupement de bin étant approximatif dans OPT + 1 est entièrement cohérent avec les connaissances actuelles. En fait, la configuration LP est conjecturée pour avoir un intervalle d'intégralité additive 1 (je trouve la conjecture un peu sauvage, mais il n'y a pas de contre-exemples connus).
Sasho Nikolov

Réponses:

23

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

Tsuyoshi Ito
la source
3
Comme autre exemple, je pense qu'il serait assez naturel de formuler le problème de la coupe maximale afin que nous maximisions la fraction des bords de la coupe. Encore une fois, nous avons des résultats positifs et négatifs pour l'approximation additive.
Jukka Suomela
1
@Jukka, pourriez-vous s'il vous plaît fournir une référence pour cette formulation de Max-cut?
Mohammad Al-Turkistany,
1
Merci beaucoup. Il semble que ce domaine doive au moins faire l'objet d'une enquête. Le zoo de la complexité ne mentionne même pas les classes d'approximation d'erreur additive pour autant que je puisse voir (bien qu'il soit si grand que j'ai peut-être manqué quelque chose).
Raphael
@Raphael: Je trouverais une enquête (ou un pointeur vers une) plutôt utile. Pour autant que je sache, les classes d'algorithmes d'approximation ont été examinées pour la dernière fois il y a environ dix ans, et j'ai trouvé la présentation loin d'être claire.
András Salamon
6

Ceci est une réponse partielle

UNEBSUNEBS

NP

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

UNEBSP=NP

Mohammad Al-Turkistany
la source
Merci. Je remarque que l'ABS n'est pas répertorié dans le zoo de la complexité qwiki.stanford.edu/index.php/Complexity_Zoo:A . Avez-vous une référence pour cela?
Raphael
Vérifiez cette référence, citeseerx.ist.psu.edu/viewdoc/…
Mohammad Al-Turkistany
Ai-je raison de penser que le nom ABS pour la classe de complexité est celui que vous venez d'inventer ou y a-t-il une référence? Le lien que vous avez publié ne semble pas le mentionner.
Raphael
@Raphael, Non, je n'ai pas inventé le nom ABS, je l'ai lu quelque part il y a longtemps.
Mohammad Al-Turkistany
6

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.

Oleksandr Bondarenko
la source