Was ist der Unterschied zwischen Online- und inkrementeller Optimierung?

8

Kürzlich habe ich einige Artikel über inkrementelle Optimierungsprobleme gelesen, aber ich kann nicht erkennen, was der Unterschied zwischen diesen und Online-Optimierungsproblemen ist. Mein Eindruck ist, dass ich jedes Online-Problem als inkrementelles Gegenstück definieren kann (das Gegenteil ist eindeutig der Fall).

Hier gehen die (nicht sehr formalen) Definitionen. In einem inkrementellen Problem erhält man eine Folge von Instanzen eines Optimierungsproblems. Die (i + 1) -te Instanz ist eine "Erweiterung" der i-ten Instanz. Die (i + 1) -te Lösung muss ohne Kenntnis der "zukünftigen" Instanzen berechnet werden und die bei der i-ten Lösung getroffenen Entscheidungen beibehalten. Das klassische Beispiel ist das k-Median-Problem: Nach dem Öffnen von k Einrichtungen möchte man k '> k Einrichtungen haben, aber die alten nicht abreißen.

In einem Online-Problem (die übliche Definition ist das) erhält man eine Folge von "Anfragen". Hier muss man auch eine Anfrage ohne Kenntnis der zukünftigen Anfragen beantworten. Man möchte die Kosten / den Gewinn für die Beantwortung der gesamten Sequenz optimieren.

Ich glaube, dass ich für jedes Online-Problem ein "Offline" -Optimierungsproblem definieren kann, das der inkrementellen Definition entspricht (und was ich normalerweise sehe, ist das Gegenteil). Wenn die Definitionen gleichwertig sind, was bringt es, für dasselbe Konzept einen anderen Namen zu verwenden?

ds.algorithms optimization online-algorithms Murilo de Lima
quelle
6
Können Sie die Definitionen von inkrementellen und Online-Optimierungsproblemen angeben? (durch Drücken der Bearbeitungsschaltfläche oben) Dadurch wird die Frage in sich geschlossen und die Community kann Ihr Problem besser verstehen, was die Wahrscheinlichkeit erhöht, dass die Frage beantwortet wird.
Hsien-Chih Chang 17 之
2
Ich kann mir vorstellen, was der Unterschied ist, aber warten wir auf die Definitionen.
Raphael

Antworten:

12

Dies wird in Abschnitt 2.2.3 der These von Jeffrey Hartline erörtert: http://www.cs.cornell.edu/w8/~jhartlin/finaldiss.pdf

Bei Online-Problemen dreht sich alles um Informationsunsicherheit: Sie wissen nicht, welche Eingaben morgen kommen, und die Schwierigkeit liegt häufig in der Informationstheorie und nicht in der Berechnung. Andererseits gibt es keine Unsicherheit bei einem inkrementellen Optimierungsproblem, wie Hartline es definiert: Jeder Parameter des Problems ist zu Beginn bekannt. Ohne Recheneinschränkungen können die Probleme immer optimal gelöst werden.

Vielleicht ist Ihre Definition falsch, da Ihre Definition tatsächlich wie ein Online-Problem klingt. Das Problem der "inkrementellen Optimierung" scheint in dieser Arbeit von 2008 definiert zu sein und unterscheidet sich von Ihrer Definition darin, dass es keine Unsicherheit gibt.

Aaron Roth
quelle
Ok, danke für den Hinweis! In der Tat ist meine Definition falsch, und tatsächlich ist die inkrementelle Optimierung allgemeiner als die Online-Optimierung.
Murilo de Lima