Kennen Sie ein aktuelles Wiki, das sich mit NP-Optimierungsproblemen befasst und deren bestes Näherungs- und Härteergebnis liefert?
Aufgrund des Feedbacks scheint es sicher zu sein, dass es keine solche Ressource gibt (siehe das Ende dieser Frage für zwei nahe Optionen). - hinzugefügt am 8. Februar.
Da in den letzten zwei Jahrzehnten eine Fülle von Ergebnissen und Problemen aufgetreten ist, könnte die Existenz eines speziellen Wikis eine große Hilfe für Studenten und Fachleute sein, die sich mit Approximationsalgorithmen und Approximationshärten befassen.
Mir wurde vorgeschlagen, ein neues Wiki zu starten. Ich mag die Idee, aber ich brauche ein Feedback, bevor ich anfange:
Interessieren Sie sich für ein Wiki, das sich mit dem oben genannten Thema befasst, und werden Sie etwas beitragen? Was ist Ihr bevorzugtes Format für dieses Wiki (siehe mein bevorzugtes Format in Kommentaren)? Sollten wir eine Wiki-Farm oder eine Wiki-Engine verwenden? In letzterem Fall, was ist Ihr Vorschlag für eine Wiki-Engine? MediaWiki?
Die beiden Optionen, die mir am nächsten kommen, sind:
1- "Ein Kompendium von NP-Optimierungsproblemen", herausgegeben von Pierluigi Crescenzi und Viggo Kann: Dieses Kompendium scheint veraltet zu sein. Ich denke, das Volumen der aktuellen Ergebnisse kann nicht von wenigen Personen verwaltet werden, und wenn wir eine aktuelle Liste wünschen, sollten wir ein Wiki haben.
2- Wikipedia: Dieses Wiki ist für das allgemeine Publikum gedacht und Sie können keine kurze Seite mit Problembeschreibung und dem besten Näherungs- und Härteergebnis haben.
Antworten:
Wenn Sie sich auf das Crescenzi-Kann-Kompendium beziehen, bin ich mir nicht sicher, ob Sie sich auf das Buch oder die Website beziehen . Das Buch ist veraltet, aber die Autoren bemühen sich, die Website ständig zu aktualisieren. Es scheint, dass der logische Ausgangspunkt darin besteht, sich mit Ihrem Vorschlag an Crescenzi und Kann zu wenden.
quelle
Complexity Garden ist ein Wiki, das sich mit Rechenproblemen und ihren Beziehungen zu Komplexitätsklassen befasst. Wie hier vorgeschlagen, hatte ich vor, ein neues Wiki für die algorithmischen Ergebnisse zu starten, aber ich dachte, wenn es ein Wiki für Rechenprobleme gibt, können wir alle Informationen an einem Ort haben. Also habe ich die Zoo-Leute kontaktiert und mit ihrer Erlaubnis den Umfang des Gartens geändert, um auch algorithmische Ergebnisse einzuschließen.
Jetzt brauche ich eine kleine Gruppe von Leuten, die mir helfen, das Wiki auf eine Größe zu erweitern, die wir öffentlich bekannt geben und mehr Mitwirkende anziehen können. Da dieses Wiki dasselbe System wie Wikipedia verwendet, dauert es durchschnittlich 15-25 Minuten, um ein Problem hinzuzufügen. Selbst wenn eine Gruppe von 5 Personen nur 3 Probleme pro Schwachstelle beisteuert (dh ungefähr 1 Stunde pro Schwachstelle), können wir 60 Probleme pro Monat hinzufügen und insgesamt 100 Probleme im Komplexitätsgarten haben.
quelle
Ja, und ich werde auf jeden Fall dafür werben!
Ich werde so viel wie möglich beitragen, aber erwarte nicht, dass ich zu den Hauptanbietern von Inhalten zähle. Wie Tsuyoshi Ito betont, kann dies zeitaufwändig werden, und ich sehe mich auch nicht als die sachkundigste Person in der Region (auf dieser Website oder anderswo).
Aber der Inhalt wird mit der Nutzerbasis sicherlich wachsen. Ich denke, Sie sollten sich nicht zu viele Sorgen machen, wenn sich die Leute dazu verpflichten, z. B. 10 Seiten pro Tag beizutragen.
Welches ist, was Garey & Johnson und Kann & Crescenzi verwenden. Probleme können auch mithilfe von Kategorien markiert werden, so dass eine Liste der Probleme nach Kategorie einfach generiert werden kann (ähnlich wie bei delicious: Klicken Sie auf das Tag "graph-theory" und sehen Sie die Liste aller schwierigen Probleme in der Grafik Theorie auf der Website).
Detailliertere Informationen könnten dann durch Klicken auf den Namen des Problems in der Liste bereitgestellt werden, die beispielsweise eine Liste "einfacher" Fälle und offener Probleme enthalten würde (z. B. "beste Annäherung ist 3/2, können wir es besser machen?"). Links zu Wikipedia oder anderen für ein breiteres Publikum, spezielle Software, ...
Sie können auch wie G & J Informationen darüber bereitstellen, wie die Ergebnisse erzielt wurden ("Transformation von X3C"). Und dann könnten Sie wahrscheinlich eine Grafik generieren, die Verringerungen zwischen verschiedenen Problemen zeigt, was die Leute dazu veranlassen würde, sich zu fragen, ob es mehr direkte Beweise gibt, aber nun ... Sie müssen irgendwo aufhören ;-)
Ich überspringe die letzte Unterfrage, weil ich keine Ahnung habe, wie ich sie beantworten soll.
quelle
Ich bin interessiert und bereit, zumindest ein wenig in meinem kleinen Fachgebiet beizutragen. Ich verstehe nicht wirklich, warum Sie Ihre Aufmerksamkeit auf die Annäherung beschränken wollen. Zum Beispiel gibt es auch ein veraltetes Kompendium parametrisierter Probleme, das sich mit Algorithmen mit festen Parametern befasst.
Auch der letzte Teil von G & J kann als NP-Härte-Kompendium angesehen werden.
IMHO, sollten Sie über ein Compendium für Computerprobleme nachdenken, in dem Sie für jedes Problem die relevantesten (guten oder schlechten) Ergebnisse angeben.
Ich stimme dem in der Antwort von Anthony Labarre vorgeschlagenen Format voll und ganz zu.
Ich bevorzuge ein selbst gehostetes Wiki, aber ein gehostetes Wiki wäre in Ordnung.
Mein einziger Vorschlag ist, dass Sie, falls Sie sich für eine Wiki-Farm entscheiden, alle Daten exportieren können. Sie können nicht sicher sein, ob die Farm eines Tages stillgelegt wird.
IMHO ist es erforderlich, eine Engine zu wählen, die das LaTeX-Format unterstützt. Mediawiki und Dokuwiki sind am weitesten verbreitet und eignen sich beide hervorragend.
Mediawiki ist etwas komplexer zu installieren und zu verwalten (ich würde sagen, mäßig komplex), aber die Syntax ist wahrscheinlich den meisten potenziellen Mitwirkenden vertraut.
Dokuwiki ist weniger umfangreich (sowohl was die benötigten Ressourcen als auch den Verwaltungsaufwand betrifft), die Syntax unterscheidet sich jedoch teilweise von der von Mediawiki.
quelle