La programmation dynamique n'est-elle jamais plus faible que Greedy?

Dans la complexité du circuit, nous avons des séparations entre les puissances des différents modèles de circuits.

Dans la complexité de la preuve, nous avons des séparations entre les puissances des différents systèmes de preuve.

Mais dans l'algorithmique, nous n'avons encore que peu de séparations entre les puissances des paradigmes algorithmiques .

Mes questions ci-dessous visent à toucher ce dernier problème pour deux paradigmes: la programmation gourmande et la programmation dynamique.

Nous avons un ensemble d'éléments au sol et une famille de ses sous-ensembles déclarés comme solutions réalisables. Nous supposons que cette famille est fermée vers le bas: des sous-ensembles de solution réalisable sont réalisables. Étant donné une affectation de poids non négatifs aux éléments de base, le problème est de calculer le poids total maximum d'une solution réalisable.

L'algorithme gourmand commence par une solution partielle vide, et à chaque étape, il ajoute un élément encore non traité de plus grand poids si cela est possible, c'est-à-dire si la solution étendue est toujours faisable. Le théorème bien connu de Rado-Edmonds déclare que cet algorithme trouvera une solution optimale pour toutes les pondérations d'entrée si la famille de solutions réalisables est un matroïde.

En gros, un algorithme DP est simple , s'il n'utilise que des opérations Max et Sum (ou Min et Sum). Pour être plus précis (comme suggéré par Joshua), par un simple algorithme DP , je veux dire un circuit (max, +) avec des portes fanin-2 Max et Sum. Les entrées sont des variables dont le ème correspond au poids donné au ème élément. Un tel circuit peut résoudre un tel problème en calculant simplement le poids total maximum d'une solution réalisable. Mais cela peut être une énorme exagération, si nous avons exponentiellement beaucoup de telles solutions (comme c'est presque toujours le cas).$i$$i$

Question 1: Existe-t-il des matroïdes sur lesquels tout algorithme DP simple aura besoin d'un nombre d'opérations super-polynomiales pour résoudre le problème de maximisation correspondant?

COMMENTAIRE (ajouté le 24.12.2015): Cette question est déjà répondue (voir ci-dessous): il existe de telles matroïdes, même dans une écrasante majorité.

La question suivante demande de séparer Greedy et DP simple pour les problèmes d' approximation . Dans le problème de correspondance de poids maximal , la famille de solutions réalisables se compose de toutes les correspondances dans le graphique bipartite complet. Pour une affectation donnée de poids à ses bords, le but est de calculer le poids maximum d'une correspondance (ce sera toujours une correspondance parfaite, car les poids ne sont pas négatifs). $n\times n$

Le simple algorithme gourmand peut approcher ce problème dans le facteur 2: il suffit de toujours prendre un bord disjoint non encore vu de poids maximal. Le poids obtenu sera au moins la moitié du poids optimal.

Question 2: Un algorithme DP simple peut-il approximer le problème de correspondance de poids maximum dans le facteur 2 en utilisant uniquement de nombreuses opérations Max et Somme polynomiales?

Bien sûr, un algorithme DP trivial, qui génère fois le poids maximum d'un bord, rapproche ce problème dans le facteur . Mais nous voulons un facteur beaucoup plus petit. Je suppose que même un facteur ne peut pas être atteint mais, encore une fois: comment le prouver ? n n / log $n$$n$$n/\log n$

CONNEXES: Un cousin de la correspondance de poids maximum est le problème d'affectation : trouvez le poids minimum d'une correspondance parfaite. Ce problème peut être résolu (même exactement) par programmation linéaire (dite algorithme hongrois) en utilisant uniquement des opérations . Mais la limite inférieure de Razborov sur la taille des circuits booléens monotones calculant la fonction permanente implique (pas tout à fait directement) que tout circuit (min, +) approximant ce problème dans n'importe quel (!) Facteur fini doit utiliser opérations. Ainsi, pour les problèmes de minimisation , les algorithmes DP simples peuvent être beaucoup plus faibles que la programmation linéaire. Mes questions ci-dessus visent à montrer que ces algorithmes DP peuvent être encore plus faibles que Greedy. n Ω ( log n $O(n^3)$$n^{\Omega(\log n)}$

Quelqu'un a-t-il vu des questions similaires examinées par quelqu'un?

---

AJOUTÉ (le 24.12.2015): La question 2 vise à montrer qu'un problème de maximisation particulier (le problème de correspondance de poids maximum), qui peut être approximé par l'algorithme gourmand avec un facteur , ne peut pas être approximé par une simple taille poly DP avec le même facteur . Pendant ce temps, j'ai obtenu une séparation plus faible entre Greedy et DP simple: pour chaque , il y a un problème de maximisation explicite qui peut être approximé par l'algorithme gourmand avec le facteur , mais pas de simple poly-taille L'algorithme DP peut approcher ce problème avec un facteur plus petit (voir ici$r=2$r = o ( n / log n ) $r$$r=o(n/\log n)$$r$$< r/3$pour un croquis). Pourtant, la question 2 elle-même (pas nécessairement pour ce problème de poids maximal particulier) reste actuelle: il serait intéressant de cibler le même facteur par les deux algorithmes.

Je pense que la réponse à ma question 1 est affirmative : il y a des matroïdes sur lesquels le simple DP échoue gravement! Autrement dit, un DP simple peut être bien pire que Greedy lorsque vous essayez de résoudre exactement un problème d'optimisation .

Soit l'ensemble de base constitué de tous les bords de . Comme notre famille de solutions réalisables prend la famille de toutes les forêts de . Ceci est une motroïde, et ses bases s'étendent sur des arbres. Ainsi, le correspondant à ce polynôme matroïde est un polynôme multilinéaire dont les monômes correspondent à des arbres couvrant. Jerrum et Snir ont prouvé (à la section 4.5) que nécessite des circuits arithmétiques monotones de taille exponentielle. Cela implique déjà que chaque circuit , et donc, également chaque algorithme DP simple, doit utiliser un nombre exponentiel d'opérations Max et Sum pour résoudre le problème d'arbre couvrant le poids maximum. K n f f ( max , + $K_n$$K_n$$f$$f$$(\max,+)$

Comme Igor Sergeev me l'a dit, une réponse affirmative à la question 1 suit également en comptant: Knuth a montré qu'il y a matroïdes sur points. $2^{2^n/n^{3/2}}$$n$

PS Je n'accepterai pas ceci ma demi-réponse (qui n'est venue qu'immédiatement après avoir repensé la connexion avec les circuits arithmétiques monotones), car une question 2 beaucoup plus intéressante reste ouverte: à quel point le DP simple peut être pire que Greedy en approximant l' optimisation problèmes? Cette question est plus intéressante, car Greedy a souvent un assez bon facteur d'approximation. Ce facteur est connu pour coïncider (!) Avec le soi-disant "quotient de rang" de la famille sous-jacente de solutions réalisables (voir, par exemple, ce résumé . Dans le cas du problème de correspondance de poids maximal, ce quotient est , et est à plus pour toute intersection dek $2$$k$$k$matroïdes. D'un autre côté, pour autant que je sache, les algorithmes d'approximation basés sur DP utilisent généralement une sorte de "mise à l'échelle" des poids d'entrée, et ne s'appliquent qu'aux problèmes de type "sac à dos" ou à des problèmes de planification. Une réponse négative à la question 2 confirmerait cette apparente "faiblesse d'approximation" de DP.