Theoretische Anwendungen für Approximationsalgorithmen

In letzter Zeit habe ich mich mit Approximationsalgorithmen für NP-schwierige Probleme befasst und mich über die theoretischen Gründe für deren Untersuchung Gedanken gemacht. (Die Frage soll nicht entzündlich sein - ich bin nur neugierig).

Einige wirklich schöne Theorien sind aus der Untersuchung von Approximationsalgorithmen hervorgegangen - der Verbindung zwischen dem PCP-Theorem und der Härte der Approximation, der UGC-Vermutung, dem Goeman-Williamson-Approximationsalgorithmus usw.

Ich habe mich allerdings gefragt, ob ich Approximationsalgorithmen für Probleme wie "Travelling Salesman", "Asymmetric Travelling Salesman" und andere Varianten, verschiedene Probleme bei der Konstruktion von Mechanismen (z. B. bei kombinatorischen Auktionen) usw. untersuchen soll. Waren solche Approximationsalgorithmen in anderen Teilen der Theorie nützlich? in der Vergangenheit oder werden sie nur für sich selbst studiert?

Anmerkung: Ich frage nicht nach praktischen Anwendungen, da meines Wissens nach in der Realität eher Heuristiken als Näherungsalgorithmen angewendet werden und die Heuristiken selten durch Erkenntnisse aus dem Studium der Näherungsalgorithmen für die Näherungsalgorithmen informiert werden Problem.

Ich stimme dem letzten Absatz überhaupt nicht zu. Pauschalaussagen wie diese sind nicht sinnvoll. Wenn Sie sich Artikel in vielen Systembereichen wie Netzwerken, Datenbanken, KI usw. ansehen, werden Sie feststellen, dass in der Praxis viele Approximationsalgorithmen verwendet werden. Es gibt einige Probleme, für die man sehr genaue Antworten wünscht; Zum Beispiel eine Fluggesellschaft, die an der Optimierung ihrer Flottenplanung interessiert ist. In solchen Fällen verwenden die Benutzer verschiedene Heuristiken, die viel Rechenzeit in Anspruch nehmen, aber bessere Ergebnisse erzielen, als ein generischer Näherungsalgorithmus liefern kann.

Nun zu einigen theoretischen Gründen für das Studium von Approximationsalgorithmen. Was erklärt zunächst die Tatsache, dass Rucksack in der Praxis sehr einfach ist, während das Färben von Grafiken ziemlich schwierig ist? Beide sind NP-Hard und Poly-Time miteinander reduzierbar. Zweitens kann man durch das Studium von Approximationsalgorithmen für spezielle Fälle eines Problems genau bestimmen, welche Klassen von Instanzen wahrscheinlich einfach oder schwierig sind. Zum Beispiel wissen wir, dass viele Probleme ein PTAS in planaren und minderwertigen Graphen zulassen, während sie in willkürlichen allgemeinen Graphen viel schwieriger sind. Die Idee der Approximation durchdringt das moderne Algorithmus-Design. Beispielsweise verwenden Menschen Datenstrom-Algorithmen, und ohne die Näherungslinse sind Algorithmen schwer zu verstehen / zu entwerfen, da selbst einfache Probleme nicht genau gelöst werden können.

$S_2^p \subseteq ZPP^{NP}$

Ich bin auch nicht einverstanden mit dem "Hinweis", zumindest in dieser Allgemeinheit angegeben. Weiß jemand im Zusammenhang damit, ob das Kanellakis-Preisgespräch von David Johnson irgendwo erhältlich ist?

Sobald wir feststellen, dass alle NP-harten Probleme in Bezug auf die Worst-Case-Komplexität der exakten Lösungen gleichwertig sind, ist es sehr natürlich, nach der Komplexität der Suche nach Näherungslösungen zu fragen. Und Chandra macht eine großartige Aussage über den Perspektivenwechsel, den Approximationsalgorithmen für das Algorithmusdesign mit sich bringen.

$O(\log n)$

Die besten Heuristiken sind wirklich Näherungsalgorithmen. Die schönsten Approximationsalgorithmen sind einfach "blöde" Heuristiken, die funktionieren. Zum Beispiel lokale Suche nach Clustering, gieriges Clustering (Gonzalez), eins zum Preis von zwei, verschiedene gierige Algorithmen usw. usw. usw.

Beim Studium von Approximationsalgorithmen geht es also wirklich darum zu verstehen, welche Heuristiken garantierte Approximationsalgorithmen sind. Die Hoffnung ist, dass die Erforschung von Approximationsalgorithmen zu zwei Arten der gegenseitigen Befruchtung führt:

• Übertragen Sie Ideen aus der Heuristik in Algorithmus-Design-Tools. Übertragen Sie Ideen aus dem Algorithmus-Design in Heuristiken / Algorithmen, die in der Praxis gut funktionieren.
• gegenseitige Befruchtung zwischen einer Person, die gerade ihren Abschluss gemacht hat, und einer Position.

Kurz gesagt, die Welt ist nicht genau, Eingaben sind nicht genau, Zielfunktionen, die durch verschiedene Algorithmusprobleme optimiert wurden, sind nicht genau und stellen bestenfalls eine unscharfe Annäherung an das dar, was man will, und Berechnungen sind nicht genau. Warum sollte jemand genaue Algorithmen lernen? (Antwort: Weil exakte Algorithmen nur wirklich gute Approximationsalgorithmen sind.)

In der realen Welt gibt es nur sehr wenige exakte Algorithmen - Sie müssen die Näherung verwenden, um aus der Ferne relevant zu sein ...

Der Umgang mit Problemen mit stetigen Variablen ist mit exakten Algorithmen sehr ärgerlich. Was bedeutet es beispielsweise, die Kantengewichte einer TSP-Instanz mit exakten reellen Zahlen anzugeben?

Wenn wir FPTAS-Algorithmen für diese Probleme zulassen, können wir diese Parameter in ganze Zahlen quantisieren. Dadurch verhält sich das Problem viel besser (es können Standard-Turing-Maschinen verwendet werden), es tritt jedoch ein kleiner Fehler auf.