L'importance de l'intégralité Gap

J'ai toujours eu du mal à comprendre l'importance de l' écart d' intégrité (IG) et des limites qui s'y rattachent. IG est le rapport entre (la qualité de) une réponse entière optimale à (la qualité de) une solution réelle optimale de la relaxation du problème. Prenons la couverture de vertex (VC) comme exemple. VC peut être indiqué comme trouvant une solution entière optimale de l'ensemble d'équations linéaires suivant:

Nous avons zéro / une des variables d'une valeur s pour chaque sommet du graphe . Les équations sont les suivantes: pour et pour chaque arête . Nous recherchons des valeurs qui minimiseront .$x_v$$v \in V(G)$$G$$0 \leq x_v \leq 1$$v\in V(G)$$1 \leq x_v+x_u$$uv \in E(G)$$\sum_{v \in V(G)} x_v$

La relaxation de ce problème autorise des valeurs réelles comprises entre et sorte que l'espace des solutions est plus grand et qu'une solution réelle optimale peut être plus petite qu'une solution entière optimale que nous voulons trouver. Par conséquent, nous devons effectuer un "arrondi" sur la réponse réelle optimale obtenue à partir de la programmation linéaire pour trouver une solution entière. La solution entière optimale se situera entre la solution réelle optimale et le résultat du processus d'arrondi. IG est le rapport entre une solution entière optimale et une solution réelle optimale et ne dit rien du processus d'arrondi. Le processus d'arrondi peut (en théorie) ignorer complètement la solution réelle et calculer directement la solution entière optimale.$0$$1$

Pourquoi les gens sont-ils intéressés à prouver des liens sur IG?

Les lacunes d'intégalité représentent essentiellement les limites inhérentes à une relaxation linéaire ou convexe particulière dans l'approximation d'un programme entier. En règle générale, si l'écart d'intégralité d'une relaxation particulière est , aucun algorithme d'approximation basé sur cette relaxation ne peut espérer faire mieux qu'une approximation . Donc, à tout le moins, les lacunes en matière d'intégralité intéressent les concepteurs d'algorithmes puisqu'elles suggèrent des limitations dans certaines techniques. $x$$x$

Alors pourquoi ne pas simplement proposer une autre relaxation LP ou passer à d’autres techniques et passer à autre chose? La programmation linéaire et convexe s'est révélée être au cœur des algorithmes d'approximation; pour de nombreux problèmes, le décalage d'intégralité d'une formulation LP ou SDP naturelle est égal au rapport d'approximation du meilleur algorithme ainsi qu'à la dureté du rapport d'approximation. Ceci est juste une observation empirique, mais cela signifie que prouver un écart d'intégralité peut suggérer des conséquences bien plus lourdes d'un algorithme amélioré ou d'une borne inférieure.

Il peut y avoir des raisons plus profondes et plus rigoureuses à ce phénomène. Par exemple, en supposant que la conjecture des jeux soit unique, il est connu que le rapport d'approximation et le taux d'inapproximabilité pour les problèmes de satisfaction de contraintes sont égaux à l'écart d'intégralité d'une relaxation SDP simple (voir Algorithmes optimaux et Résultats d'inapproximabilité pour chaque CSP? De Prasad Raghavendra)

Enfin, les écarts d’intégralité représentent des limites inférieures inconditionnelles . Habituellement, nous devons nous appuyer sur des hypothèses non prouvées (par exemple, ) si nous voulons progresser dans les limites inférieures, mais dans le cas de modèles de calcul restreints, nous pouvons parfois nous en passer (voir notes de lecture de Luca Trevisan). Les écarts d’intégrité, qui sont purement géométriques plutôt que calculatoires, sont un moyen d’obtenir des bornes inférieures assez puissantes sans le bagage d’hypothèses supplémentaires.$P \neq NP$

Supposons que votre problème d'intérêt est un problème de minimisation et que vous avez développé un algorithme -approximate. Si, sur une entrée donnée, votre algorithme génère une solution de coût , alors le calcul de l'algorithme et son analyse donnent un certificat qui, sur cette entrée, l'optimum est au moins . Clairement, est au moins l'optimum, donc pour chaque entrée nous pouvons certifier une limite inférieure à l'optimum qui est au moins une fraction de de l'optimum lui-même.c a / c a 1 /$a$$c$$a/c$$a$$1/c$

Dans tous les algorithmes basés sur les relaxations convexes (LP et SDP) que je connaisse, la limite inférieure certifiée à l'optimum est donnée par l'optimum de la relaxation. Si la relaxation présente un écart d'intégralité , il ne sera pas possible d'obtenir un rapport d'approximation supérieur à , à moins que , dans l'analyse, on introduise une technique de la limite inférieure de l'optimum plus forte que la limite inférieure fournie par la relaxation.$I$$I$

L'écart d'intégralité est un indicateur utile de la qualité approximative d'une IP. Il serait peut-être préférable d'y penser d'une manière informelle et intuitive. Un écart d'intégalité élevé implique que certaines méthodes ne fonctionneront pas. Certaines méthodes primales / doubles, par exemple, dépendent d'un petit écart d'intégalité. Pour le disque primal standard Vertex Cover LP, le double disque demande une correspondance maximale. Dans ce cas, nous pouvons procéder comme suit:

• trouver une solution fractionnelle optimale à la double LP (une correspondance fractionnaire maximale)$\boldsymbol{y}$
• multiplier la solution par un facteur de 2 (doubler tous les poids des arêtes)$\boldsymbol{y}$
• convertissez-le en une intégrale réalisable pour le premier LP (chaque arête donne la moitié de son poids du vecteur à chacune de ses extrémités dans le vecteur , puis chaque est remplacé par ).$\boldsymbol{x}$$2\boldsymbol{y}$$\boldsymbol{x}$$x_i$$\min(\lfloor x_i\rfloor, 1)$

Dans ce cas, cette stratégie simple fonctionne et nous aboutissons à une solution intégrale réalisable pour le disque primaire primal dont le poids n’est pas plus de deux fois supérieur à celui d’une solution réalisable pour le disque dual. Étant donné que le poids d'une solution réalisable pour le double disque est une limite inférieure pour l'OPT, il s'agit d'un algorithme à 2 approximations.

Maintenant, où se situe le fossé de l'intégralité? L'IG est 2 dans ce cas, mais cela ne signifie pas que l'algorithme fonctionnera. Cela suggère plutôt que cela pourrait fonctionner. Et si l'IG était supérieur à 2, cela garantirait que la stratégie simple ne fonctionnera pas toujours. À tout le moins, il faudrait multiplier la double solution par l'IG. Ainsi, le fossé de l'intégralité nous dit parfois ce qui ne fonctionnera pas . L'écart d'intégralité peut également indiquer le type de facteur d'approximation que nous pouvons espérer. Un petit écart d'intégralité suggère que la recherche de stratégies d'arrondissement, etc., pourrait être une approche intéressante.

Pour un exemple plus intéressant, considérons le problème Hitting Set et la technique puissante permettant d’approcher le problème en utilisant -nets (Brönnimann & Goodrich, 1995) . De nombreux problèmes peuvent être formulés en tant qu'instances de Hitting Set, et une stratégie qui a réussi pour de nombreux problèmes consiste à le faire. Il suffit ensuite de trouver un bon chercheur de réseau, à savoir un algorithme pour construire de petits réseaux , et de tout mettre en marche. le méta-algorithme B & G. Donc, les gens (moi compris) essaient de trouver des chercheurs d’internet pour des instances restreintes de Hitting Set qui, pour tout , peut construire un -net de taille , où la fonction$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$f(1/\varepsilon)$$f$devrait être aussi petit que possible. Avoir est un objectif typique; cela donnerait une approximation .$f(1/\varepsilon) = \mathcal{O}(1/\varepsilon)$$\mathcal{O}(1)$

En fin de compte, la meilleure fonction est limitée par le décalage d’ intégrité de certains disques pour Hitting Set (Even, Rawitz, Shahar, 2005) . Plus précisément, les solutions intégrales et fractionnaires optimales satisfont . Pour les instances non restreintes de Hitting Set, l’intégralité de l’écart est de , mais lors de la formulation d’un autre problème sous le nom de Hitting Set, l’IG peut être inférieur. Dans cet exemple, les auteurs montrent comment trouver -nets de taille$f$$\mathrm{OPT}_I \leq f(\mathrm{OPT}_f)$$\Theta(\log(m))$$\varepsilon$$\mathcal{O}((1/\varepsilon) \log \log (1/\varepsilon))$pour les occurrences limitées de Hitting Set qui correspondent au problème de la frappe de cases parallèles à l'axe. De cette manière, ils améliorent le facteur d'approximation le plus connu pour ce problème. C'est un problème ouvert si cela peut ou non être amélioré. Si, pour ces occurrences restreintes du groupe de frapper, l'IG pour le groupe de frapper LP est , il serait impossible de concevoir un détecteur de réseau garantissant des -nets de taille , car cela impliquerait l’existence d’un algorithme garantissant des ensembles de frappes intégrales de taille , mais depuis$\Theta(\log \log m)$$\varepsilon$$o((1/\varepsilon) \log \log (1/\varepsilon))$$o(\mathrm{OPT}_f \log\log \mathrm{OPT}_f)$$\mathrm{OPT}_f\leq m$cela impliquerait un plus petit écart d'intégralité. Donc, si le fossé de l'intégralité est grand, prouver qu'il pourrait empêcher les gens de perdre leur temps à chercher de bons trouveurs de réseaux.

Lorsque vous proposez un algorithme d’approximation pour un problème de maximisation NP-hard, vous pouvez vous préoccuper de plusieurs valeurs: Il existe OPT, la valeur optimale de votre problème, qui est identique à OPT (IP), la valeur optimale. valeur de toute formulation IP correcte de votre problème. Il existe également OPT (LP), la valeur optimale de la relaxation linéaire de votre IP.

$OPT(LP) \geq OPT(IP)$

Enfin, il y a V, la valeur de la solution que vous obtenez en arrondissant la solution LP. Vous voudriez pouvoir prouver que montre que votre algorithme est une approximation de , mais il est souvent impossible de le faire directement, car vous n'avez pas maintenez l'espace de la solution. Au lieu de cela, ce qui est presque toujours prouvé, c’est que . Ceci implique bien sûr , mais est plus fort. En particulier, si le décalage d'intégralité de votre formulation IP est supérieur à , la déclaration ci-dessus sera généralement fausse, car votre procédure d'arrondi aboutira à une solution intégrale.$V > \frac{OPT(IP)}{c}$$c$$V \geq \frac{OPT(LP)}{c}$$V > \frac{OPT(IP)}{c}$$c$

Le problème est donc le suivant: le disque vous donne une solution que vous savez "bonne" et que vous voulez arrondir à quelque chose qui est "presque aussi bon". Si le fossé de l'intégralité est grand, c'est généralement impossible, car il n'y aura jamais de procédure garantissant d'obtenir une solution intégrale aussi "aussi bonne" qu'une solution LP - parce que parfois, elles n'existent pas!

Vous avez raison de dire que l'écart d'intégralité d'une relaxation n'a en soi rien à voir avec un algorithme d'arrondi. Ce sont deux notions différentes. Un écart d'intégralité est une propriété d'une relaxation particulière. Autrement dit, quelle est la valeur de cette relaxation par rapport à la valeur intégrale optimale?

Pourquoi nous intéressons-nous aux relaxations linéaires / convexes? Pour approcher efficacement une valeur intégrale. Par conséquent, nous ne parlons généralement de relaxations que dans les cas où la valeur optimale est difficile à calculer et nous nous intéressons aux approximations efficaces. Les lacunes en matière d'intégralité nous montrent les limites inhérentes à ce que peuvent réaliser ces techniques.

Alors, pourquoi nous intéressons-nous aux algorithmes d'arrondi en plus de la relaxation? Nous utilisons des algorithmes d'arrondi pour résoudre le problème algorithmique consistant à trouver une solution quasi optimale, par opposition à une simple approximation de la valeur d'une solution optimale. De plus, des algorithmes d'arrondi sont souvent utilisés pour limiter l'écart d'intégralité d'une relaxation.

Techniquement, l’écart d’intégralité concerne une formulation IP spécifique et non (comme vous l’avez formulé) le rapport entre la meilleure relaxation linéaire et la solution optimale (qui semble quantifier l’ensemble des formulations IP).

Un écart d'intégralité est important car il montre les limites de la formulation LP utilisée. Si je sais qu’une relaxation particulière a un écart d’intégralité de , alors je sais aussi que si j’espère jamais prouver un lien de meilleur que , j’aurai besoin d’une formulation différente.$c$$c$

Il y avait un article très intéressant "Sur l’avantage du codage réseau pour améliorer le débit du réseau", qui montrait que l’écart d’intégalité de la "relaxation de coupe orientée par bidirectionnel" pour le problème de l’arbre de Steiner équivaut exactement à un type "d’avantage de codage" dans la communication réseau. Je ne connais pas beaucoup d'autres documents similaires. Cependant, il convient également de noter que l'on connaît apparemment de meilleures relâchements de LP pour le problème de l'arbre de Steiner (voir par exemple le nouvel algorithme d'approximation hypergraphique basé sur les LP de Byrka et al dans STOC 2010). LP).

La plupart des réponses ont déjà abordé la principale raison de se préoccuper de l'écart d'intégralité, à savoir qu'un algorithme d'approximation basé uniquement sur l'utilisation de la borne fournie par la relaxation ne peut espérer prouver un rapport meilleur que l'écart d'intégralité. Permettez-moi de donner deux autres méta-raisons pour lesquelles l'écart d'intégralité est un guide utile. Pour une large classe de problèmes d'optimisation combinatoire, l'équivalence de la séparation et de l'optimisation montre que les algorithmes exacts sont intimement liés à l'enveloppe convexe des solutions possibles pour le problème. Ainsi, les perspectives géométrique et algorithmique sont très étroitement liées. Une équivalence formelle similaire n'est pas connue pour les algorithmes d'approximation, mais c'est un guide utile - les algorithmes vont de pair avec les relaxations géométriques. L'innovation algorithmique se produit lorsque les personnes ont un objectif concret à améliorer.