Algorithmes gloutons optimaux pour les problèmes NP-difficiles

La cupidité, faute d'un meilleur mot, est bonne. L' approche gloutonne est l'un des premiers paradigmes algorithmiques enseignés dans le cours d'introduction aux algorithmes . Une approche gloutonne donne des algorithmes simples et intuitifs pour de nombreux problèmes de P. Plus intéressant, pour certains problèmes complexes, l'algorithme glouton / local évident et naturel résulte en un facteur d'approximation (prouvable) optimal (sous des hypothèses théoriques de complexité appropriées). Un exemple classique est le problème de la couverture d'ensemble . Un algorithme glouton naturel donne un facteur d'approximation O (ln n) optimal, sauf si P = NP.

Nommez des algorithmes naturels gloutons / locaux pour les problèmes NP-difficiles qui sont manifestement optimaux sous des hypothèses théoriques de complexité appropriées.

La méthode des attentes conditionnelles (pour dérandonner les algorithmes "d'assignation aléatoire" pour Max-Cut et Max-SAT) peut être considérée comme une stratégie gloutonne: pour , vous choisissez la valeur d'une variable x i telle que le nombre attendu de contraintes satisfaites dans l'instance réduite résultante dépasse le nombre attendu de contraintes satisfaites dans l'instance actuelle. (En fait, l'algorithme glouton pour une /$i=1,\ldots,n$$x_i$$1/2$ -approximating Max-Cut est la même que la "méthode des attentes conditionnelles" algorithme de -approximating Max-Cut.)$1/2$

Etant donné que la méthode fonctionne également pour Max-E3-SAT et réalise un -approximation, ceci est un exemple d'un algorithme glouton qui est une approximation optimale de moins que$7/8$ (cf. Hastad et Moshkovitz-Raz 'Résultats de inapproximabilité pour Max -E3-SAT).$P=NP$

Couverture de vertex: Le meilleur algorithme d'approximation en facteurs constants consiste à trouver (avec avidité) une correspondance maximale et à choisir tous les sommets impliqués comme solution approchée. Cela donne une solution approximative à deux et aucune meilleure approximation à facteur constant n'est possible à moins que la conjecture de Games unique ne soit fausse.

Subhash Khot et Oded Regev, la couverture de Vertex pourrait être difficile à estimer à 2 − −2, JCSS 74 (3), 2008.

Hors sujet: Je pense que c'est un algorithme d'approximation vraiment mignon, d'autant plus qu'il est tellement trivial avec l'avantage du recul.

Étant donné un graphe orienté, trouvez le sous-graphe acyclique avec le nombre maximum d’arêtes.

Algorithme à 2 approximations trivial: Choisissez un ordre arbitraire des sommets et prenez les arêtes avant ou arrière.

Battre l'approximation 2 est connu pour être Unique-games hard (bien que cela ne soit peut-être pas NP-difficile).

• Il est difficile de battre l'ordre aléatoire: l'inapproximabilité du sous-graphe acyclique maximum Venkatesan Guruswami, Rajsekar Manokaran et Prasad Raghavendra.

La maximisation submodulaire par rapport à la contrainte de cardinalité a une approximation gloutonne de 1-1 / e. L'algorithme est dû à Nemhauser, Wolsey, Fisher. La dureté NP résulte de np-hardness de la couverture du set, car la max-couverture est un cas particulier de maximisation sous-modulaire.

Greedy donne une approximation (1-1 / e) de Max-k-cover et ne peut être améliorée que si P = NP.

Trouver un degré minimum MST. Il est difficile car trouver un chemin hamiltonien est un cas particulier. Un algorithme de recherche locale donne à l'intérieur d'une constante additive 1.

Référence

Rapprocher l’arbre de Steiner au degré minimum à l’un des meilleurs.

Le problème des centres est un problème de groupement, dans lequel on nous donne un graphe complet non orienté G = ( V , E ) avec une distance d i j ≥ 0 entre chaque paire de sommets i , j ∈ $k$$G = (V,E)$$d_{ij} \geq 0$$i,j \in V$$k$

$k$$S \subseteq V, |S| = k$$k$$k$$k$$r$$r$ soit le plus petit possible.

$i \in V$$S$$|S| < k$$j \in V$$d(j,S)$$S$$|S| = k$

$2$$k$$\rho$$\rho < 2$$P = NP$$k$$k$ problème du centre où toutes les distances sont 1 ou 2 a une valeur optimale 1. L'algorithme et l'analyse sont donnés par Gonzales, Clustering pour minimiser la distance maximale entre les grappes, 1985$2$

La procédure d'ordonnancement de liste de Graham est optimale pour l'ordonnancement contraint de priorité sur des machines identiques $P|prec|C_{max}$ à moins qu'une nouvelle variante de la conjecture unique des jeux de Bansal et Khot soit fausse.

Dureté conditionnelle de priorité Ordonnancement contraint sur des machines identiques par Ola Svensson

Peut-être que cela vous intéresserait également (adapté de Méthodes pour traduire les contraintes globales en contraintes locales )

Etant donné que les méthodes gourmandes (plus correctement les méthodes locales ) n'utilisent que des informations locales pour obtenir une optimisation globale, si l'on trouve des moyens capables de transformer des conditions globales en conditions pouvant être utilisées en utilisant uniquement des informations locales, ceci fournit une solution (globale) optimale aux problèmes utilisant uniquement des techniques gourmandes / locales.

Les références:

1. Penser globalement et en forme localement: apprentissage non supervisé des variétés multiples de dimension (Journal of Machine Learning Research 4 (2003))
2. Optimisation globale en utilisant des informations locales avec des applications pour contrôler le flux, Bartal, Y.
3. Pourquoi un gradient naturel ?, Amari S., Douglas SC
4. Optimisation locale des objectifs globaux: résolution des impasses distribuées concurrentielles et allocation des ressources, Awerbuch, Baruch, Azar, Y.
5. Apprendre avec la cohérence locale et globale
6. Problèmes de satisfaction des contraintes pouvant être résolus par les méthodes de cohérence locale

Quelques références abordent le problème de la traduction des fonctions d'évaluation globales (ou contraintes) en fonctions locales (en utilisant des informations locales) et leur cohérence (c'est-à-dire la convergence vers le même optimum global):

1. Fonctions d'évaluation locale et Fonctions d'évaluation globale pour l'évolution informatique, HAN Jing, 2003
2. Émergence de la fonction d'évaluation locale, Han Jing et Cai Qingsheng, 2002

Résumé (de 1. ci-dessus)

Cet article présente un nouveau regard sur l'évolution des calculs sous l'angle de la localisation et de la globalité des fonctions d'évaluation permettant de résoudre le problème combinatoire classique: le problème kcoloring (problème de décision) et le problème de coloration minimum (problème d'optimisation). Nous passons d’abord en revue les algorithmes actuels et modélisons le problème de coloration sous la forme d’un système multi-agents. Nous montrons ensuite que la différence essentielle entre les algorithmes traditionnels (Recherche locale, telle que l'annulation simulée) et les algorithmes distribués (tels que le modèle Alife & AER) réside dans la fonction d'évaluation: L'annulation simulée utilise des informations globales pour évaluer l'état complet du système, appelé la méthode de la fonction d'évaluation globale (FEM); le modèle Alife & AER utilise des informations locales pour évaluer l'état d'un agent unique, qui s'appelle la méthode de la fonction d'évaluation locale (LEF). Nous comparons les performances des méthodes LEF et GEF pour résoudre les problèmes de k-coloration et les problèmes de coloration minimum. Les résultats expérimentaux sur ordinateur montrent que le LEF est comparable aux méthodes du FEM (recuit simulé et Greedy). Dans de nombreux cas, le LEF bat les méthodes du FEM. Dans le même temps, nous analysons la relation entre FEM et LEF: cohérence et incohérence. Le théorème de cohérence montre que les équilibres de Nash d'un LEF sont identiques aux optima locaux d'un FEM, lorsque le LEF est cohérent avec le FEM. Ce théorème explique en partie pourquoi le LEF peut mener le système vers un objectif global. Quelques règles pour la construction d’un LEF cohérent sont proposées. En plus de la cohérence,

Le document traite en particulier des méthodes permettant de déterminer si une fonction locale (LEF) est cohérente avec une fonction globale (GEF) et des méthodes permettant de construire des LEF cohérents à partir de GEF donnés ( théorème de cohérence ).

Extrait de la section Conclusion (à partir de 1. ci-dessus)

Ce document n’est que le début des études LEF & GEF. Outre le rapport de recherche ci-dessus, de nombreux travaux sont encore à venir: davantage d'expériences sur les méthodes LEF; étude analytique sur le LEF; suffisance des informations locales pour le LEF; et l'existence d'un FEM cohérent pour toute LEF; Le concept de cohérence est-il suffisant? Puisque les algorithmes génétiques ont également une fonction d'évaluation (fonction de fitness), pouvons-nous appliquer LEF & GEF aux algorithmes génétiques? … Nous avons l'intention d'étudier et d'essayer de répondre à toutes ces questions