Co to jest algorytm aproksymacji bicriteria?

Co to jest algorytm aproksymacji bicriteria? Nadal pojawia się to w przypadku klastrowania strumienia danych. Czy ma to związek z optymalizacją wielu celów?

Właśnie tam natknąłem się na: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. Artykuł dotyczy strumieniowej wersji algorytmu k-średnich. W pracy znajdują się odniesienia, ale żadne z nich nie wyjaśnia, czym jest algorytm aproksymacji bicriteria. Nie mogę też znaleźć w Google niczego, co dałoby mi dokładną definicję.

Będę rozwinąć odpowiedź Yuval Filmus poprzez dostarczenie interpretacji na podstawie wielu obiektywnych problemów optymalizacyjnych .

Optymalizacja i przybliżenie jednego celu

W informatyce często badamy problemy z optymalizacją z jednym celem (na przykład minimalizować f ( x ) z zastrzeżeniem pewnych ograniczeń). Udowadniając, powiedzmy, kompletność NP, często bierze się pod uwagę odpowiedni problem budżetowy . Na przykład w przypadku problemu maksymalnej kliki celem jest maksymalizacja liczności kliki, a problemem budżetowym jest problem decydowania, czy istnieje klika o wielkości co najmniej k , gdzie k jest podawane jako część danych wejściowych do problem.

Gdy nie jest możliwe skuteczne obliczenie optymalnego rozwiązania, jak w przypadku problemu maksymalnej klikalności, szukamy algorytmu aproksymacji , funkcji, która generuje rozwiązanie w ramach mnożnika optymalnego rozwiązania. Można również rozważyć algorytm aproksymacji dla problemu budżetowego, funkcję, która generuje rozwiązanie, które spełnia f ( x ) ≥ ck w przypadku problemu maksymalizacji, gdzie c jest liczbą mniejszą niż jeden. W tej sytuacji rozwiązanie może naruszać twarde ograniczenie f ( x ) ≥ k , ale „dotkliwość” naruszenia jest ograniczona przez c .

Optymalizacja wielu celów i aproksymacja dwukryterialna

W niektórych przypadkach możesz chcieć zoptymalizować dwa cele jednocześnie. Na przykład mogę chcieć zmaksymalizować mój „przychód”, jednocześnie minimalizując mój „koszt”. W takiej sytuacji nie ma jednej optymalnej wartości, ponieważ istnieje kompromis między dwoma celami; Aby uzyskać więcej informacji, zobacz artykuł w Wikipedii o wydajności Pareto .

Jednym ze sposobów przekształcenia problemu optymalizacji z dwoma celami w problem optymalizacji z jednym celem (dla którego możemy uzasadnić optymalną wartość funkcji celu) jest rozważenie dwóch problemów z ograniczeniami , po jednym dla każdego celu. Jeśli problemem jest jednoczesna maksymalizacja f ( x ) przy minimalizacji g ( x ), pierwszym problemem związanym z ograniczeniem jest zminimalizowanie g ( x ) z zastrzeżeniem ograniczenia f ( x ) ≥ k , gdzie k jest podane jako część danych wejściowych do ten problem optymalizacji z jednym celem. Drugi problem z ograniczeniami jest zdefiniowany podobnie.

Algorytm aproksymacji bikriteriów ( α , β ) dla pierwszego problemu z ograniczeniami jest funkcją, która przyjmuje parametr budżetowy k jako dane wejściowe i wysyła rozwiązanie x takie, że

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

$x^*$

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

Innymi słowy, algorytm aproksymacji bicriteria jest jednocześnie przybliżeniem problemu budżetowego w pierwszym celu i problemem optymalizacji w drugim celu. (Ta definicja została zaadaptowana ze strony czwartej „ Optymalizacja Submodular z Pokryciem Submodular i Ograniczeniami Plecaka Submodular ”, Iyer i Bilmes, 2013.)

Nierówności zmieniają kierunki, gdy cele zmieniają się z maksimum na minimum lub odwrotnie.

$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$

Innymi słowy, algorytm aproksymacji bicriteria osiąga pewien współczynnik aproksymacji, naruszając pewne ograniczenie o pewną ograniczoną ilość. Przykład algorytmu aproksymacji bicriteria dla właśnie opisanego problemu można znaleźć w tym artykule braci Makarychev.