Écart d'intégrité et rapport d'approximation

Lorsque nous considérons un algorithme d'approximation pour un problème de minimisation, l'écart d'intégralité d'une formulation IP pour ce problème donne une limite inférieure d'un rapport d'approximation pour certaines classes d'algorithmes (comme l'arrondi ou l'algorithme primal-dual). En fait, il existe de nombreux problèmes dont le meilleur rapport d'approximation correspond à l'écart d'intégralité.

Certains algorithmes peuvent avoir un meilleur rapport d'approximation que l'écart d'intégralité pour certains problèmes, mais je ne sais pas si un tel exemple existe ou non. Si la réponse est oui, pourriez-vous donner quelques exemples?

Je sais que certains problèmes admettent plusieurs formulations mathématiques. Dans de tels cas, considérez la formulation mathématique avec le plus petit écart d'intégralité, tant qu'elle peut être résolue en temps polynomial (peut-être que certaines formulations peuvent utiliser des oracles de séparation).

Cette question est liée à [la question: L'importance de l'écart d'intégrité] .

ds.algorithms approximation-algorithms linear-programming integrality-gap Snowie
la source

Je suppose que le TSP géométrique serait un exemple d'un tel problème, mais je n'ai aucune référence.

Jukka Suomela

Et qu'en est-il des problèmes qui admettent un PTAS utilisant la stratégie de déplacement? Y a-t-il une formulation IP avec un écart d'intégralité arbitrairement petit?

Jukka Suomela

@Jukka TSP géométrique en est un bon exemple. L'exemple de l'écart d'intégralité 4/3 est une métrique de chemin le plus court sur un graphe planaire, et il devrait être possible de se transformer en une instance de TSP euclidien ou de TSP dans le plan avec un écart de

ℓ_{1}

$\ell_1$

1 + ϵ

$1+\epsilon$

Luca Trevisan

Je l'ai entendu mentionné comme une question ouverte intéressante si les PTAS pour les problèmes sur les graphes planaires peuvent être réalisés en utilisant un nombre constant de niveaux de relaxations Sherali-Adams ou Lasserre. (Lorsque la constante dépend de la ration d'approximation que l'on veut atteindre.) Il devrait être connu, ou du moins prouvable avec les techniques actuelles, que les problèmes de graphes qui ont des PTAS dans des graphes denses (par exemple, coupe maximale) ont également une famille de polynômes. relaxations de taille avec des écarts d'intégralité arbitrairement petits.

Luca Trevisan

Question connexe: Existe-t-il un problème prouvé qu'un LP de taille polynomiale ne peut pas donner le meilleur rapport d'approximation actuellement connu? Est-il possible de prouver une telle chose, même pour certains types de LP limités?

Danu

Réponses:

Comme indiqué, il existe de nombreux exemples.

Un exemple classique est l'appariement maximal, où la relaxation "naturelle" (sans contraintes d'ensemble impair) a un écart de 2, alors qu'il existe bien sûr un algorithme efficace. Cependant, celui-ci n'est pas entièrement qualifié, car il existe un LP de taille exponentielle qui peut être résolu via un ellipsoïde.

Un intrigant est l'emplacement de l'installation capacitée. Ici, la relaxation naturelle a un écart d'intégralité illimité. Pourtant, les algorithmes basés sur la recherche locale donnent des approximations de facteurs constants.

Un autre très intéressant (bien que ce soit un problème de maximisation) est cet article: http://www.cis.upenn.edu/~sanjeev/postscript/FOCS09_MaxMin.pdf . Ici, le LP a un grand écart, et pourtant un algorithme qui utilise ce LP peut faire mieux.

Kunal
la source

Merci beaucoup. Cette réponse contient ce que je cherchais, en particulier l'article FOCS écrit par Chakrabarty et al. (ce papier m'intéresse tellement). Par conséquent, j'ai défini cette réponse comme acceptée. Je cherche toujours plus d'exemples et donc toute personne qui peut donner d'autres exemples serait très appréciée.

Snowie

Il existe divers exemples dans lesquels une relaxation de programmation semi-définie permet une approximation supérieure aux lacunes d'intégralité connues pour les relaxations de programmation linéaire.

Par exemple, la relaxation de programmation linéaire standard de la coupe maximale a un écart d'intégralité de 1/2, et cela est vrai même pour les relaxations de programmation linéaire beaucoup plus sophistiquées (cf. de la Vega-Kenyon et Schoenebeck-Trevisan-Tulsiani), mais les Goemans -L'algorithme de Williamson SDP a une approximation .878 ...

$\Omega(\log n)$ $O(\sqrt{\log n})$

Peut-être moins bien connu, Karloff et Zwick montrent que l'utilisation de SDP peut approximer Max 3SAT, dans la version dans laquelle les clauses peuvent avoir 1, 2 ou 3 littéraux, en 7/8, tandis que Goemans et Williamson avaient étudié une relaxation de programmation linéaire qu'ils utilisé pour prouver une approximation de 3/4 (Yannakakis avait donné une approximation de 3/4 plus tôt par d'autres méthodes), et la relaxation Goemans-Williamson LP de Max 3SAT est facilement considérée comme ayant un écart d'intégralité de 3/4.

Luca Trevisan
la source

Grant a également obtenu un résultat sur la résolution de systèmes linéaires sur GF_2. Pour les systèmes d'équations avec une bonne solution, vous avez un écart d'intégralité SDP (sous une forme très forte) de 2 tandis que vous pouvez utiliser l'élimination gaussienne pour résoudre le problème exactement.

YI WU
la source