Was ist ein Bicriteria-Approximationsalgorithmus?

Was ist ein Bicriteria-Approximationsalgorithmus? Dies tritt im Fall von Datenstrom-Clustering immer wieder auf. Bezieht sich dies auf die Optimierung mehrerer Ziele?

Hier bin ich darauf gestoßen: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. Das Papier handelt von einer Streaming-Version des k-means-Algorithmus. Es gibt Referenzen in der Arbeit, aber keine von ihnen gibt eine Erklärung dafür, was ein Bicriteria-Approximationsalgorithmus ist. Ich kann bei Google anscheinend nichts finden, was mir eine genaue Definition geben könnte.

Ich werde die Antwort von Yuval Filmus durch eine Interpretation erweitern, die auf Optimierungsproblemen mit mehreren Zielen basiert .

Einzelzieloptimierung und -näherung

In der Informatik untersuchen wir Optimierungsprobleme häufig mit einem einzigen Ziel (z. B. minimieren Sie f ( x ) unter bestimmten Bedingungen). Wenn beispielsweise die NP-Vollständigkeit nachgewiesen wird, ist es üblich, das entsprechende Budgetproblem zu berücksichtigen . Beispielsweise besteht beim Problem der maximalen Clique das Ziel darin, die Kardinalität der Clique zu maximieren, und das Budgetproblem besteht darin, zu entscheiden, ob es eine Clique mit einer Größe von mindestens k gibt , wobei k als Teil der Eingabe an gegeben wird das Problem.

Wenn es nicht möglich ist, eine optimale Lösung effizient zu berechnen, wie im Fall des Maximum-Clique-Problems, suchen wir einen Approximationsalgorithmus , eine Funktion, die eine Lösung innerhalb eines multiplikativen Faktors einer optimalen Lösung ausgibt. Sie können auch einen Näherungsalgorithmus für das Budgetproblem in Betracht ziehen, eine Funktion, die eine Lösung ausgibt, die f ( x ) ≥ ck im Fall eines Maximierungsproblems erfüllt , bei dem c eine Zahl kleiner als eins ist. In dieser Situation kann die Lösung die harte Bedingung f ( x ) ≥ k verletzen , aber die "Schwere" der Verletzung ist durch c begrenzt .

Mehrzieloptimierung und Bi-Kriterium-Approximation

In einigen Fällen möchten Sie möglicherweise zwei Ziele gleichzeitig optimieren. Als grobes Beispiel möchte ich vielleicht meinen "Umsatz" maximieren und gleichzeitig meine "Kosten" minimieren. In einer solchen Situation gibt es keinen einzigen optimalen Wert, da zwischen den beiden Zielen ein Kompromiss besteht. Weitere Informationen finden Sie im Wikipedia-Artikel zur Pareto-Effizienz .

Eine Möglichkeit, ein Optimierungsproblem mit zwei Zielen in ein Optimierungsproblem mit einem Ziel umzuwandeln (für das wir über den optimalen Wert der Zielfunktion nachdenken können), besteht darin, die beiden Einschränkungsprobleme zu berücksichtigen , eines für jedes Ziel. Wenn das Problem darin besteht, gleichzeitig f ( x ) zu maximieren, während g ( x ) minimiert wird , besteht das erste Beschränkungsproblem darin, g ( x ) zu minimieren , das der Beschränkung f ( x ) ≥ k unterliegt , wobei k als Teil der Eingabe an gegeben ist dieses einzielige Optimierungsproblem. Das zweite Einschränkungsproblem ist ähnlich definiert.

Ein ( α , β ) - Bicriteria-Approximationsalgorithmus für das erste Beschränkungsproblem ist eine Funktion, die einen Budgetparameter k als Eingabe verwendet und eine Lösung x so ausgibt, dass

• $f(x) \geq \alpha k$
• $g(x) \leq \beta g(x^*)$

$x^*$

• $f(x) \geq \alpha f(x^*)$
• $g(x) \leq \beta \ell$

Mit anderen Worten ist der Bicriteria-Approximationsalgorithmus gleichzeitig eine Appoximation für das Budgetproblem im ersten Ziel und das Optimierungsproblem im zweiten Ziel. (Diese Definition wurde von Iyer und Bilmes, 2013, aus Seite 4 von " Submodulare Optimierung mit submodularer Abdeckung und submodularen Rucksackbeschränkungen " übernommen.)

Die Ungleichungen wechseln die Richtung, wenn die Ziele von Maximum zu Minimum oder umgekehrt wechseln.

$k$$\rho$$k$$V_1,\ldots,V_k$$\rho$$E(V_1,\ldots,V_k)$$\rho$

$f(n),g(n) \geq 1$$f(n),g(n)$$V_1,\ldots,V_k$$f(n)\rho$$g(n)\mathrm{OPT}$$\mathrm{OPT}$$\rho$.

In other words, a bicriteria approximation algorithm achieves a certain approximation ratio while violating some constraint by some bounded amount. For an example of a bicriteria approximation algorithm for the problem just described, see this paper by the Makarychev brothers.