Compendium des meilleurs résultats d'approximation et de dureté pour les problèmes d'optimisation NP

26

Connaissez-vous un wiki à jour dédié aux problèmes d'optimisation NP avec leur meilleur résultat d'approximation et de dureté?

Sur la base des commentaires, il semble qu'il est prudent de supposer qu'il n'y a pas une telle ressource (voir la fin de cette question pour deux options proches). - ajouté le 8 février.

Puisqu'il y a un énorme corpus de résultats et de problèmes introduits au cours des deux dernières décennies, l'existence d'un wiki dédié pourrait être d'une grande aide pour les étudiants et les professionnels travaillant sur le sujet des algorithmes d'approximation et de la dureté de l'approximation.

On m'a suggéré de créer un nouveau wiki. J'aime l'idée, mais j'ai besoin de quelques commentaires avant de commencer:
Êtes-vous intéressé par un wiki consacré au sujet ci-dessus et allez-vous contribuer quelque chose? Quel est votre format préféré pour ce wiki (voir mon format préféré dans les commentaires)? Faut-il utiliser une ferme wiki ou un moteur wiki? Dans ce dernier cas, quelle est votre suggestion pour un moteur wiki? MediaWiki?

Les deux options les plus proches que je connaisse sont:
1- "Un recueil de problèmes d'optimisation NP", édité par Pierluigi Crescenzi et Viggo Kann: Ce recueil semble être obsolète. Je pense que le volume des résultats actuels ne peut pas être géré par quelques personnes et si nous voulons une liste à jour, nous devrions avoir un wiki.
2- Wikipédia: Ce wiki est destiné au grand public et vous ne pouvez pas avoir une courte page comprenant simplement la description du problème et le meilleur résultat d'approximation et de dureté.

ds.algorithms reference-request approximation-algorithms approximation-hardness Babak Behsaz
la source
1
Je pense que nous pouvons conclure sans risque qu'il n'y a pas de telles ressources.
Jukka Suomela
3
@Suresh Je pensais à une courte page contenant uniquement une description du problème (c'est-à-dire des instances, des solutions et la fonction objective) et les meilleurs résultats d'approximation et de dureté avec leurs hypothèses respectives et ne contenant pas d'historique, de motivation, de description d'algorithme, etc. Une page avec ce format est plus facile à créer et vous pouvez trouver les résultats les plus récents plus rapidement qu'une page wikipedia. Le recueil édité par Crescenzi et Kann correspond à ce profil, mais ce n'est pas un wiki et donc, il est obsolète.
Babak Behsaz
8
vous avez alors besoin de quelque chose comme le zoo de la complexité. vous devriez peut-être en créer un et solliciter des bénévoles d'ici pour l'aider à le remplir.
Suresh Venkat
2
Un wiki serait utile. Cependant, je pense que cela devrait être plus que simplement le problème et le résultat le plus connu. Le problème avec cette approche est qu'elle sera principalement utile aux théoriciens alors qu'une page contenant plus d'informations sera probablement utile aux praticiens; on peut parler de cas particuliers connus et de résultats connexes, etc. Pourquoi ne pas utiliser pleinement les liens, commentaires, références, etc.?
Chandra Chekuri
2
Peu importe ce que vous finissez par faire, je vous recommande fortement d'essayer d'établir des liens entre des résultats comme le zoo de complexité. Il est utile de savoir qu'une amélioration de l'approximation pour le problème X implique quelque chose pour Y, et ainsi de suite. De plus, la hiérarchie des hypothèses de dureté de David Johnson (dans une colonne récente) devrait également exister.
Suresh Venkat

Réponses:

9

Lorsque vous faites référence au recueil Crescenzi-Kann, je ne sais pas si vous faites référence au livre ou au site Web . Le livre est obsolète mais les auteurs essaient de maintenir le site Web constamment mis à jour. Il semblerait que le point de départ logique soit d'approcher Crescenzi et Kann avec votre proposition.

Timothy Chow
la source
Il est bon de savoir que les auteurs sont disposés à maintenir le site Web constamment mis à jour. J'ai eu l'impression qu'ils ont arrêté la mise à jour en mars 2000 car la plupart des pages disent qu'elles ont été mises à jour pour la dernière fois le 2000-03-20.
Tsuyoshi Ito, le
3
Je parle du site Web. Je ne sais pas s'ils le modifient plus activement. Je me souviens avoir signalé une amélioration du taux d'approximation d'un problème, mais ils ne l'ont pas mis à jour. Quoi qu'il en soit, je conviens qu'il est logique de contacter Crescenzi et Kann concernant le statut de leur recueil et la possibilité de le changer en wiki.
Babak Behsaz
1
@Suresh @Anthony @Florent @Tsuyoshi @Jukka @Gianluca: Je n'ai pas pu trouver les coordonnées de (Dr.?) Pierluigi Crescenzi. J'ai donc envoyé un e-mail au professeur Kann le 9 février et je n'ai pas reçu de réponse. Le 16 février, j'ai envoyé mon e-mail précédent aux sous-éditeurs des professeurs Karpinski et Woeginger du recueil, mais encore une fois je n'ai pas reçu de réponse. J'ai envoyé les deux e-mails avec mon adresse e-mail universitaire, donc je suppose qu'ils ne se sont pas retrouvés dans leurs dossiers de spam. Quelle est votre suggestion maintenant?
Babak Behsaz
Je suppose qu'un nouveau wiki pourrait alors être lancé. Si à un moment donné les auteurs du recueil original s'en plaignent, une solution sera facilement trouvée (par exemple fusionner les deux ressources existantes)
Florent Foucaud
@Babak: Si vous êtes toujours intéressé, vous pouvez trouver l'e-mail du professeur Crescenzi ici
Gianluca Della Vedova
7

Complexity Garden est un wiki consacré aux problèmes de calcul et à leurs relations avec les classes de complexité. Comme suggéré ici, je prévoyais de démarrer un nouveau wiki pour les résultats algorithmiques, mais je pensais que quand il y a un wiki pour les problèmes de calcul, nous pouvons avoir toutes les informations en un seul endroit. J'ai donc contacté les gens du Zoo et avec leur permission, j'ai changé la portée du Jardin pour inclure également les résultats algorithmiques.

Maintenant, j'ai besoin d'un petit groupe de personnes pour m'aider à remplir le wiki à une taille que nous pouvons annoncer publiquement et attirer plus de contributeurs. Comme ce wiki utilise le même système que wikipedia, il faut en moyenne 15-25 minutes pour ajouter un problème. Ainsi, même avec un groupe de 5 personnes ne contribuant qu'à 3 problèmes par faible (soit environ 1 heure par faible), nous pouvons ajouter 60 problèmes en un mois et avoir un total de 100 problèmes dans le Complexity Garden.

Babak Behsaz
la source
1
Quel est le statut de votre initiative?
Florent Foucaud
Je ne vois aucun ajout sur cette page après le 25 août, donc je suppose que Babak s'est découragé par manque de participants. J'ai raté cette annonce et j'essaierai de contribuer dès que possible.
Anthony Labarre
1

Êtes-vous intéressé par un wiki consacré au sujet ci-dessus

Oui, et je vais certainement en faire la publicité!

et allez-vous contribuer quelque chose?

Je contribuerai autant que possible, mais ne vous attendez pas à ce que je fasse partie des principaux fournisseurs de contenu. Comme le souligne Tsuyoshi Ito, cela peut prendre beaucoup de temps, et je ne me considère pas non plus comme la personne la plus compétente dans la région (sur ce site Web ou ailleurs).

Mais le contenu finira certainement par croître avec la base d'utilisateurs, donc je ne pense pas que vous devriez trop vous soucier d'avoir des personnes engagées à contribuer, par exemple 10 pages par jour chacune.

Quel est votre format préféré pour ce wiki (voir mon format préféré dans les commentaires)?

jeth

je

  • Instance: ...
  • Question: ...
  • Références: Pour la dureté, voir [i1], pour l'inapproximabilité, voir [i2], ...

C'est ce qu'utilisent Garey & Johnson's et Kann & Crescenzi. Les problèmes peuvent également être marqués à l'aide de catégories comme bon nous semble, de sorte qu'une liste de problèmes par catégorie puisse être facilement générée (un peu comme sur delicious: cliquez sur la balise "graph-theory", et consultez la liste de tous les problèmes difficiles dans le graphique théorie sur le site).

Des informations plus détaillées pourraient alors être fournies en cliquant sur le nom du problème dans la liste, qui contiendrait par exemple une liste de cas "faciles", des problèmes ouverts (par exemple "la meilleure approximation est 3/2, pouvons-nous faire mieux?") liens vers Wikipedia ou autres pour un public plus large, logiciels spécialisés, ...

Vous pouvez également, comme l'a fait G&J, fournir des informations sur la manière dont les résultats ont été obtenus ("transformation à partir de X3C"). Et puis vous pourriez probablement générer un graphique montrant des réductions entre différents problèmes, ce qui amènerait les gens à se demander s'il existe des preuves plus directes, mais bon ... vous devez vous arrêter quelque part ;-)

Je vais sauter la dernière sous-question car je ne sais pas comment y répondre.

Anthony Labarre
la source
Je pense que démarrer un wiki ne nécessite pas trop d'efforts. Il vous suffit de configurer un moteur wiki (cela ne devrait pas être si difficile), d'écrire une page principale, d'écrire une page sur le format obligatoire des pages et de composer un exemple de page (par exemple pour le problème de la couverture). Le reste peut se faire au fil du temps. Cela peut sembler un peu simpliste, mais je pense que s'il y a suffisamment d'intérêt de la part de la communauté théorique, les problèmes seront résolus au fil du temps et le wiki grandira.
Babak Behsaz
1
@Babak: Je pense que vous avez vraiment besoin d'un vrai contenu pour commencer. Ce vrai contenu peut être copié-collé du recueil si les auteurs en sont satisfaits. Il est difficile d'imaginer qu'une boîte vide uniquement avec un système attirera les utilisateurs.
Tsuyoshi Ito
@Ito Je pense qu'au début, la majorité des utilisateurs seront ceux qui veulent contribuer au wiki, pas nécessairement l'utiliser. Je ne sais pas combien de membres de la communauté aiment contribuer de cette manière, mais j'aurais moi-même fait cela s'il y avait un wiki presque vide. Le fait est qu'entre deux choix de ne pas avoir de wiki ou d'avoir un système de travail vide, lequel est le meilleur. Je pense que ce dernier est inoffensif. Si nous pouvons trouver des personnes qui souhaitent mettre plus d'efforts sur le wiki (par exemple, copier les matériaux du recueil avec la permission), alors c'est parfait.
Babak Behsaz
Copier (avec permission) le contenu du recueil ne devrait pas être trop difficile et sera suffisant pour un point de départ. En fait, pourquoi ne pas proposer aux auteurs de transformer le recueil existant en wiki?
Florent Foucaud le
2
@Babak: Je suis d'accord qu'un système de travail vide est inoffensif. Je veux juste maximiser la probabilité de réussite. Pour ce faire, je pense que le vrai contenu est un facteur clé. J'espère que les auteurs du recueil actuel sont prêts à le changer en wiki.
Tsuyoshi Ito le
1

Êtes-vous intéressé par un wiki consacré au sujet ci-dessus et allez-vous contribuer quelque chose?

Je suis intéressé et je suis prêt à contribuer, au moins un peu dans mon petit domaine d'expertise. Je ne comprends pas vraiment pourquoi vous voulez limiter votre attention à l'approximation. Par exemple, il existe également un recueil obsolète des problèmes paramétrés consacré aux algorithmes à paramètres fixes.

En outre, la dernière partie de G&J peut être considérée comme un recueil de dureté NP.

À mon humble avis, vous devriez penser à un recueil de problèmes de calcul où, pour chaque problème, vous énoncez les résultats les plus pertinents (bons ou mauvais).

Quel est votre format préféré pour ce wiki (voir mon format préféré dans les commentaires)?

Je suis entièrement d'accord avec le format proposé dans la réponse d'Anthony Labarre.

Faut-il utiliser une ferme wiki ou un moteur wiki?

J'ai une légère préférence pour un wiki auto-hébergé, mais un wiki hébergé conviendrait.

Ma seule suggestion est que, si vous choisissez une batterie de serveurs wiki, assurez-vous de pouvoir exporter toutes les données. Vous ne pouvez pas être sûr que la ferme sera fermée un jour.

Dans ce dernier cas, quelle est votre suggestion pour un moteur wiki? MediaWiki?

À mon humble avis, une exigence est de choisir un moteur prenant en charge le format LaTeX. Mediawiki et Dokuwiki sont les plus répandus et sont tous deux d'excellents choix.

Mediawiki est un peu plus complexe à installer et à gérer (je dirais modérément complexe) mais sa syntaxe est probablement familière à la plupart des contributeurs potentiels.

Dokuwiki est plus léger (en termes de ressources nécessaires et d'efforts de gestion) mais la syntaxe est en partie différente de celle de Mediawiki.

Gianluca Della Vedova
la source