Przykłady zabawek dla solverów Plotkin-Shmoys-Tardos i Arora-Kale

Chciałbym zrozumieć, w jaki sposób solver Arora-Kale SDP aproksymuje relaksację Goemansa-Williamsona w prawie liniowym czasie, jak solver Plotkin-Shmoys-Tardos aproksymuje ułamkowe problemy „upakowania” i „pokrycia” w prawie liniowym czasie oraz jak algorytmy są instancjami abstrakcyjnych ram „uczenia się od ekspertów”.

Teza Kale'a ma doskonałą prezentację, ale bardzo trudno mi przejść bezpośrednio do abstrakcyjnych ram i wolałbym zacząć od przykładu prostego problemu, dla którego jest absolutnie oczywiste, co robić, a następnie przejść do bardziej ogólnych problemów , stopniowo dodając „funkcje” do algorytmu i jego analizy.

Na przykład:

W jaki sposób Plotkin-Shmoys rozwiązuje relaksację programowania liniowego nieważonej osłony wierzchołków? Ważona pokrywa wierzchołków? Ustawić ochronę? Dwustronne dopasowanie?

Jaki jest najprostszy przykład, w którym algorytm Arora-Kale robi coś interesującego? Jak oblicza największą wartość własną Laplaciana na wykresie?

(Obliczenie największej wartości własnej Laplaciana jest równoznaczne z problemem rozwiązania słabszej wersji relaksacji SDP Goemans-Williamson Max Cut, w której zamiast wymagać, aby każdy wektor miał długość jeden, potrzebujesz sumy kwadratów norm, które mają być | V |.)

Luca, odkąd minął rok, prawdopodobnie badałeś własną odpowiedź. Odpowiadam na niektóre z twoich pytań tutaj dla przypomnienia. Przeglądam niektóre algorytmy relaksacyjne Lagrangiana pod kątem wspomnianych problemów i szkicuję związek z uczeniem się (w szczególności zgodnie z poradami ekspertów). Nie komentuję tutaj algorytmów SDP.

Zauważ, że określone algorytmy, o których wspominasz, nie działają w czasie prawie liniowym. (Istnieje algorytm czasu prawie liniowego dla jawnie zadawanych problemów z pakowaniem lub pokrywaniem. Zobacz Beating Simplex w przypadku ułamkowego pakowania i obejmowania programów liniowych .) Algorytmy, o których myślisz, zazwyczaj mają warianty, które działają w prawie liniowej liczbie iteracji , ale każdy z nich iteracja zazwyczaj wymaga również co najmniej czasu liniowego. Poniżej omawiam niektóre z tych algorytmów.

Niektóre przydatne funkcje

Zanim zaczniemy, oto kilka funkcji, które wykorzystamy w szkicach próbnych. (Jeśli interesują Cię algorytmy, ale nie szczegóły, możesz przeskoczyć do przodu.) Dla dowolnego wektora zdefiniuj na . Ta funkcja jest górną granicą : Analogicznie zdefiniuj na , dolna granica na .$y$$\mbox{Lmax}(y)$$\ln \sum_i \exp(y_i)$$\max_i y_i$min i y i

$$\max_i y_i ~\le~ \mbox{Lmax}(y) ~\le~ \max_i y_i + \ln m.$$ $\mbox{Lmin}(y)$$-\mbox{Lmax}(-y)$$\min_i y_i$

Dla wygody poniżej używamy do oznaczenia gradientu Lmin. Używamy do oznaczenia gradientu Lmax.$g(y)$$\nabla \mbox{Lmin}(y)$$G(y)$$\nabla \mbox{Lmax}(y)$

Oczywiście, to podczas gdy to .$g_i(y)$$\exp(-y_i)/\sum_{i'} \exp(-y_{i'})$$G_i(y)$$\exp(y_i)/\sum_{i'} \exp(y_{i'})$

Lmin i Lmax są płynne w tym sensie: dla dowolnych wektorów oraz , i $d\in[0,\varepsilon]^n$$y\in R^n$

$$\mbox{Lmin}(y+d) ~\ge~ \mbox{Lmin}(y) ~+~ (1-O(\varepsilon))\, d \cdot g(y)$$ $$\mbox{Lmax}(y+d) ~\le~ \mbox{Lmax}(y) ~+~ (1+O(\varepsilon))\, d \cdot G(y).$$

Zauważ, że oba gradienty mają 1-normę równą 1: . (W całym używamy do oznaczenia 1-normy).$|G(y)| = |g(y)| = 1$$|z|$

Zauważ również, że dla macierzy gradient funkcji w odniesieniu do wynosi (według reguły łańcucha) . Mówiąc dokładniej, pochodna cząstkowa funkcji względem to . Podobnie częściowa pochodna Lmax w odniesieniu do to .$A$$x\mapsto \mbox{Lmin}(Ax)$$x$$(g(Ax))^T A$$x_j$$\sum_i A_{ij} \exp(-A_i x) / \sum_i \exp(-A_i x)$$(Ax)$$x_j$$\sum_i A_{ij} \exp(A_i x)/\sum_i \exp(A_i x)$

Fractional Set Cover

Napraw instancję Set-Cover. Niech oznacza macierz padania elementu / zestawu. Zatem jeśli , w przeciwnym razie 0, a jest zakresem, w którym ułamkowa pokrywa obejmuje element .$A$$A_{es} = 1$$e\in s$$A_e x$$x$$e$

LP to . Biorąc pod uwagę , algorytm jest$\min\{ |x| : A x \ge 1; x \ge 0\}$$\varepsilon\in (0,1)$

---

1. Zainicjuj wszystkie . Niech . $x_s = 0$$N=\log(n)/\varepsilon$

2. Powtarzaj, aż : $\min_e A_e x \ge N$

   2.1 Wybierz maksymalizując pochodną cząstkową Lmin wrt . (Jawnie wybierz maksymalizowanie .) $s$$(Ax)$$x_s$ s ∑ e ∈ s exp ( - ∑ s ′ ∋ e x s ′ )
   $s$$\sum_{e\in s} \exp(-\sum_{s'\ni e} x_{s'})$

   2.2 Zwiększ o . $x_s$$\varepsilon$

3. Zwróć .$x/\min_{e} A_e x$

---

Algorytm zwraca przybliżone rozwiązanie w iteracjach , gdzie jest liczbą elementów, a jest optymalnym ułamkowy zestaw okładek (trywialnie ). (Podobny algorytm pojawia się we wspomnianej pracy Chandra . Wierzchołek to oczywiście szczególny przypadek).$(1+O(\varepsilon))$$O(|x^*|\log(n)/\varepsilon^2)$$n$$x^*$$|x^*|\le n$

( Uwaga: Należy zauważyć, że granica iteracji nie zależy od liczby zestawów, tylko od liczby elementów. W związku z tym algorytm może być stosowany z domyślnie zdefiniowanym systemem zestawów, pod warunkiem, że przy danym ciężarze elementów można skutecznie znajdź zestaw maksymalnej (lub prawie maksymalnej) masy całkowitej. Ten rodzaj wyroczni jest taki sam jak wyrocznia separacyjna wymagana do zastosowania algorytmu elipsoidy do podwójnego problemu. W przypadku problemów związanych z pakowaniem, takich jak pakowanie zestawów, potrzebujesz wyroczni, która: podane wagi na elementach, zwraca zestaw minimalizujący całkowitą wagę. W przypadku problemów takich jak przepływ wielu towarów, możesz na przykład znaleźć ścieżkę minimalizującą sumę niektórych podanych wag krawędzi.)

Oto szkic dowodu gwarancji wydajności. W każdej iteracji pochodna częściowa wr wybranego wynosi co najmniej, gdzie jest optymalnym pokryciem zestawu ułamkowego.$s$$1/|x^*|$$x^*$

(Aby zobaczyć dlaczego, przypomnijmy sobie, że gradient Lmin w stosunku do wynosi . Gdybyśmy mieli wybrać zbiór losowo z rozkładu oczekiwana wartość pochodnej cząstkowej w odniesieniu do wynosiłaby zatem . Od , to wynosi co najmniej . Ponieważ , jest to co najmniej . Zatem muszą istnieć pewne dające pochodną cząstkową co najmniej . Ponieważ algorytm wybiera$(Ax)$$x$$(g(Ax))^T A$$s'$$x^*/|x^*|$$x_{s'}$$(g(Ax))^T \,A x^*/|x^*|$$Ax^* \ge 1$$|g(Ax)|/|x^*|$$|g(Ax)|=1$$1/|x^*|$$s$$1/|x^*|$$x_s$w każdej iteracji, aby zmaksymalizować pochodną cząstkową, uzyskuje pochodną cząstkową o wartości co najmniej.) 1 / | x ∗ |$1/|x^*|$

Następnie rozmiar kroku jest wybierany na tyle mały, że żadna współrzędna wzrasta o więcej niż . Zatem, ze względu na gładkość Lmin, zwiększenie do zwiększa o co najmniej .$\varepsilon$$A x$$\varepsilon$$x_s$$x_s+\varepsilon$$\mbox{Lmin}(Ax)$$(1-O(\varepsilon))\varepsilon/|x^*|$

W ten sposób algorytm utrzymuje niezmiennik (Zauważ, że Lmin jest równy .)

$$\mbox{Lmin}(Ax) \ge (1-O(\varepsilon)) |x|/|x^*| - \ln n.$$ $(\overline 0)$$\ln n$

W momencie zakończenia, w niezmienniku, to razy lewa strona, więc według obliczeń otrzymujemy. Po normalizacji w ostatnim wierszu algorytmu oznacza to.$\ln n$$O(\varepsilon)$$\min_e A_e x \ge (1-O(\varepsilon)) |x|/|x^*|$$|x| \le (1+O(\varepsilon))|x^*|$

FWIW, nierówności związane z udowodnieniem niezmiennika są zasadniczo takie same jak te związane z udowodnieniem granicy z Chernoffem. (W rzeczywistości algorytm ten można uzyskać, stosując metodę prawdopodobieństw warunkowych do schematu zaokrąglania losowego, który wielokrotnie próbkuje zestawy z rozkładu (z zamianą), zwiększając dla każdego próbkowanego zestawu Ta derandomizacja daje algorytm: niezmiennikiem leżącym u podstaw jest po prostu to, że estymator pesymistyczny pozostaje poniżej 1. Wykładnicze kary w estymatorze pesymistycznym wynikają z zastosowania granicy Chernoffa w analizie schematu zaokrąglania. we wspomnianym artykule Chandra .)$x^*/|x^*|$$x_s$$s$

Fractional Weighted Set Cover (i ogólne Fractional Covering)

Aby efektywnie radzić sobie z problemami takimi jak Weighted Set Cover , modyfikujemy algorytm, aby używał niejednorodnych przyrostów (pomysł dzięki Garg i Konemann ).

LP to , gdzie rozciąga się na elementy, rozciąga się na zestawy, a wszystkie zmienne nie są -negatywny. Aby przedstawić algorytm, najpierw przepisz problem jako ogólny problem obejmujący. Niech dla A przeciwnym razie. Następnie (ze zmianą zmiennych, skalowanie każdego przez ), LP to , które możemy postrzegać jako ogólne obejmujące LP. Oto algorytm:$\min\{ c\cdot x : (\forall e) \sum_{s\ni e} x_s \ge 1\}$$e$$s$$A_{es} = 1/c_s$$e\in s$$A_{es} = 0$$x_s$$c_s$$\min\{ |x| : A x \ge 1; x \ge 0\}$

---

1. Zainicjuj wszystkie . Niech .$x_s = 0$$N=\log(n)/\varepsilon$

2. Powtarzaj, aż wszystkie ograniczenia obejmujące zostaną usunięte:

   2.1 Wybierz maksymalizując pochodną cząstkową Lmin wrt . (Jawnie wybierz maksymalizowanie .)$s$$(Ax)$$x_s$ s ∑ e ∈ s exp ( - ∑ s ′ ∋ e x s ′ ) / c s
   $s$$\sum_{e\in s} \exp({-\sum_{s'\ni e} x_{s'}})/c_s$

   2.2 Zwiększ o , gdzie jest wybierane maksymalnie tak, że dla każdego pozostałego ograniczenia pokrycia wzrost wynosi najwyżej .$x_s$$\delta$$\delta$$e$$A_e \cdot x$$\varepsilon$

   2.3 Usunięcie wszystkich ograniczeń obejmujące , tak że .$e$$A_e\cdot x \ge N$

3. Zwraca .$x/\min_e A_e\cdot x$

---

Algorytm zwraca przybliżone rozwiązanie w iteracjach , gdzie jest liczbą obejmujących ograniczeń. (Każda iteracja zwiększa część pozostałego o ; może się to zdarzyć tylko razy do ograniczenia przed jego usunięciem.) Dowód poprawności jest zasadniczo taki sam niezmienny jak dla Set Cover.$(1+O(\varepsilon))$$O(n\log(n)/\varepsilon^2)$$n$$A_e x$$\varepsilon$$N/\varepsilon$

Ważona osłona wierzchołków to specjalny przypadek.

Maksymalne ułamkowe dopasowanie dwustronne

Biorąc pod uwagę wykres , naturalny LP dla problemu to .$G=(U,W,E)$$\max\{|x| : \forall v.\, \sum_{e\ni v} x_e \le 1\}$

W reprezentacji macierzowej jest to pakujący LP o współczynnikach 0-1 ( jeśli ). Takie problemy nie wymagają nierównomiernych przyrostów, więc prosty algorytm analogiczny do nieważonego algorytmu Set Cover (ale do pakowania) wykona:$\max\{|x| : Ax \le 1; x \ge 0\}$$A_{ve} = 1$$v\in e$

---

1. Zainicjuj wszystkie . Niech .$x_e = 0$$N=\log(n)/\varepsilon$

2. Podczas gdy :$A x < N$

   2.1 Wybierz minimalizując pochodną cząstkową Lmax wrt . (Jawnie wybierz aby zminimalizować .)$e$$(Ax)$$x_e$ e ∑ v ∈ e exp ( ∑ e ′ ∋ v x e ′ )
   $e$$\sum_{v\in e} \exp(\sum_{e'\ni v} x_{e'})$

   2.2 Zwiększ o . $x_e$$\varepsilon$

3. Zwraca .$x/\max_{v} A_v x$

---

Algorytm zwraca przybliżone rozwiązanie w iteracjach . (Jest tak, ponieważ każda iteracja zwiększa o , a na koniec, przed normalizacją, .)$(1-O(\varepsilon))$$O(n\log(n)/\varepsilon^2)$$|x|$$\varepsilon$$|x| = O(N n)$

Dla zabawy, oto ciekawy alternatywny algorytm dla Perfect Bipartite Matching. Przypomnij sobie, że . Niech.$G=(U,W,E)$$n=|U|=|W|$

---

1. Zainicjuj wszystkie . Niech . $x_e = 0$$N=4\ln(n)/\varepsilon$

2. Powtórz razy:$n\,N$

   2.1 Wybierz równomiernie losowo z . 2.2 Wybierz , aby minimalizowanie . 2.3 Zwiększ o . $u$$U$
   $w$$(u,w)\in E$$\sum_{e\ni w} x_e$
   $x_{uw}$$\varepsilon$

3. Powrót .$x/N$

---

Jeśli ma idealne dopasowanie, algorytm zwraca taką, że , i z dużym prawdopodobieństwem dla wszystkich wierzchołków , , a dla wszystkich wierzchołków , . Jeśli jesteś zainteresowany szczegółami dowodu, zapytaj ...$G$$x$$|x|=n$$u\in U$$1-O(\varepsilon) \le \sum_{e\ni u} x_e \le 1+O(\varepsilon)$$w\in W$$\sum_{e\ni w} x_e \le 1+O(\varepsilon)$

Mieszane pakowanie i przykrycie

Być może zapytałeś o dwustronne dopasowanie, mając nadzieję na przykład problemu mieszanego pakowania i pokrycia, czyli jednej z postaci Oto jeden algorytm dla takich problemów. Najpierw normalizacji tak że i .

$$\exists x?~ Px \le p; Cx \ge c; x \ge 0.$$ $p=\overline 1$$c=\overline 1$

Niech będzie liczbą ograniczeń (rzędy w plus rzędy w ).$m$$P$$C$

---

1. Zainicjuj wszystkie . Niech .$x_j = 0$$N=2\ln(m)/\varepsilon$

2. Podczas gdy :$P x < N$

   2.1 Wybierz aby częściowa pochodna Lmax w odniesieniu do była co najwyżej częściową pochodną Lmin w odniesieniu do . (Jawnie wybierz , aby$j$$(Px)$$x_j$$(Cx)$$x_j$$j$

   $$\frac{\sum_i P_{ij} \exp(P_i x)}{\sum_{i}\exp(P_i x)} \le \frac{\sum_i C_{ij} \exp(-C_i x)}{\sum_{i}\exp(-C_i x)}.)$$

   2.2 Zwiększ o , gdzie jest wybierane maksymalnie tak, aby żadne ograniczenie lub pozostałe ograniczenie wzrosło o więcej niż .$x_j$$\delta$$\delta$$P_i x$$C_i x$$\varepsilon$

   2.3 Usuń wszystkie obejmujące ograniczeń takie, które .$i$$C_i x \ge N$

3. Zwraca .$x/\max_i P_i x$

---

Zakładając, że dany problem jest wykonalny, algorytm zwraca takie, że i . Liczba iteracji wynosi , ponieważ każda iteracja zwiększa pewne ograniczenie o , i może się to zdarzyć dla każdego ograniczenia najwyżej razy.$x$$Px\le 1$$Cx\ge 1-O(\varepsilon)$$O(m\ln(m)/\varepsilon^2)$$\varepsilon$$N$

Dowodem poprawności jest niezmiennik Niezmiennik implikuje Po zakończeniu po lewej stronie znajduje się , co potwierdza gwarancję wydajności.

$$\mbox{Lmax}(Px) \le 2\ln(m) + (1+O(\varepsilon)) \mbox{Lmin}(Cx).$$ $$\max Px \le 2\ln(m) + (1+O(\varepsilon)) \min Cx.$$ $\Omega(\log(m)/\varepsilon)$

W kroku 2.1 pożądane musi istnieć tak długo, jak długo oryginalny problem jest wykonalny. (Jest tak, ponieważ dla każdego możliwego i dowolnego , jeśli wybralibyśmy losowe z rozkładu , oczekiwana wartość pochodnej cząstkowej Lmax w odniesieniu do wynosiłoby co najwyżej (patrz poprzedni szkic dowodu dla Zestawu okładki). Podobnie, oczekiwana wartość częściowej pochodnej Lmin w odniesieniu do będzie wynosić co najmniej . Zatem istnieje$j$x ∗ x j ′ x ∗ / | x ∗ | ( P x ) x j ′ 1 / | x ∗ | ( C x ) x j ′ 1 / | x ∗ | j ( P x ) x j ′ ( C x ) $x^*$$x$$j'$$x^*/|x^*|$$(Px)$$x_{j'}$$1/|x^*|$$(Cx)$$x_{j'}$$1/|x^*|$$j$tak, że częściowa pochodna Lmax w odniesieniu do jest co najwyżej częściową pochodną Lmin .)$(Px)$$x_{j'}$$(Cx)$

Następnie niezmiennik jest utrzymywany w każdej iteracji, ponieważ poprzez wybór i oraz gładkość Lmin i Lmax, zwiększenie do zwiększa Lmax maksymalnie o razy wzrost Lmin .$x_j$$\delta$$x_j$$x_j+\delta$$(Px)$$1+O(\varepsilon)$$(Cx)$

Uczenie się (obserwowanie ekspertów / wzmacnianie)

Jednym z odniesień do zrozumienia tego związku jest gra adaptacyjna z wykorzystaniem mnożników , autorstwa Freunda i Schapire'a. Oto krótkie podsumowanie przedstawiające pomysł techniczny.

Rozważ następującą powtarzaną grę. W każdej rundzie : $t$

1. Ty wybierasz rozkład prawdopodobieństwa na ( tak zwanych ekspertach ). $p^t$$[n]$$n$
2. Znając , przeciwnik wybiera wektor wypłaty . $p^t$$a^t\in [0,1]^{n}$
3. Otrzymujesz wypłatę za rundę. $p^t\cdot a^t$

Gra kończy się po pewnej liczbie rund. Twoim celem jest, aby zminimalizować swój żal w stosunku do każdego pojedynczego eksperta (czyli czysta Strategia) . Oznacza to, że Twoim celem jest zminimalizowanie .$i$$(\max_i \sum_t a^t_i) - \sum_t p^t\cdot a^t$

Napraw dowolne . Niech wektor oznacza , to znaczy razy suma wektorów wektorów wypłat do czasu . Przypomnij sobie, że jest gradientem Lmax .$\varepsilon>0$$y^t$$\varepsilon \sum_{s \le t} a^s$$\varepsilon$$t$$G(y)$$(y)$

Oto podstawowa strategia, którą przeanalizujemy: W rundzie wybierz jako .$t$$p^t$$G(y^{t-1})$

Przez kontrolę daje to wypłatę w rundzie .$a^t \cdot G(y^{t-1})$$t$

Ze względu na właściwość gładkości , Oznacza to, że w każdej rundzie nie może wzrosnąć więcej niż razy twoja wypłata. Ponieważ , zachowuje to niezmienność, że to co najwyżej całkowity czas wypłaty , plus . Z drugiej strony żałujesz w porównaniu z najlepszym ekspertem jest , tj.$F$

$$\mbox{Lmax}(y^t) \le \mbox{Lmax}(y^{t-1}) + (1+O(\varepsilon)) \varepsilon a^t \cdot G(y^{t-1}).$$ $\mbox{Lmax}(y^t)$$\varepsilon(1+O(\varepsilon))$$\mbox{Lmax}(\overline 0) = \ln n$$\mbox{Lmax}(y^t)$$\varepsilon(1+O(\varepsilon)$$\ln(n)$$i$$\max_i \sum_t a^t_i$$\varepsilon^{-1} \max_i y^t_i$, co z kolei co najwyżej .$\varepsilon^{-1} \mbox{Lmax}(y^t)$

Dlatego żałujesz co najwyżej plus razy łączna wypłata.$\varepsilon^{-1} \ln(n)$$O(\varepsilon)$

Uwaga: Myślę, że, jak wskazują Freund i Schapire, algorytm „wzmacniający” (w teorii uczenia się) jest również zawarty w tej analizie. Zobacz ich artykuł, aby uzyskać więcej informacji.

Minimalizowanie całkowitej wypłaty

Możesz opracować podobną strategię dla ustawienia, w którym celem jest zminimalizowanie , a nie maksymalizacja całkowitej wypłaty. Żałujesz, że nadal chcesz zminimalizować, to . W takim przypadku odpowiednią strategią jest wybranie jako gradientu . Dzięki tej strategii ponownie żałujesz co najwyżej plus razy łączna wypłata.$\sum_t p^t\cdot a^t - \min_i a^t_i$$p^t$$\mbox{Lmin}(y^t)$$\varepsilon^{-1} \ln n$$O(\varepsilon)$

Połączenie z algorytmami relaksacji Lagrangiana

Aby zobaczyć połączenie z algorytmami relaksacyjnymi Lagrangian, napraw instancję Set-Cover. Rozważ ten drugi rodzaj gry (w celu zminimalizowania wypłaty), w którym eksperci odpowiadają elementom twojego zestawu gier . W każdej rundzie wybierz rozkład prawdopodobieństwa aby był gradientem Lmin jak powyżej, i niech przeciwnik wybierze wektor wypłaty jako funkcję w następujący sposób: wybierz zestaw maksymalizowanie , następnie pozwól jeśli , a przeciwnym razie.$e$$p^t$$(y^t)$$a^t$$p^t$s t ∑ e ∈ s p t e a t e = 1 e ∈ s t a t e = 0$s^t$$\sum_{e\in s} p^t_e$$a^t_e = 1$$e\in s^t$$a^t_e = 0$

Biorąc pod uwagę poprawny warunek zatrzymania (omówiony poniżej), proces ten daje dokładnie algorytm Set-Cover omówiony na początku.

Gwarancja wydajności algorytmu wynika z żalu związanego w następujący sposób. Niech będzie liczbą razy, gdy przeciwnik wybrał zestaw podczas gry. Niech będzie optymalnym pokryciem zestawu ułamkowego. Niechbyć liczbą rozegranych rund. Granica żalu oznacza $X_s$$s$$x^*$$T=|X_s|$

$$\textstyle \sum_t a^t\cdot p^t \le \varepsilon^{-1}\ln(m) + \min_e \sum_t a_e^t.$$

Zgodnie z definicją z , do p wypłat (w termin TH suma po lewej stronie) jest równa . Przeciwnik wybrał zminimalizowanie tego wypłat. Jeśli przeciwnik zamiast tego wybrał losowo z rozkładu, oczekiwanie wypłaty to (Powyżej wykorzystujemy tę dla wszystkich , i ). Ponieważ każda wypłata przynajmniej$a^t$$t$$t$$\sum_{e\in s^t} p^t_e$$s^t$$s^t$$x^*/|x^*|$

$$\sum_s \frac{x^*_s}{|x^*|} \sum_{e\in s} p^t_e ~=~ \frac{1}{|x^*|} \sum_e p^t_e \sum_{s\ni e} x^*_s ~\ge~ \frac{1}{|x^*|} \sum_e p^t_e ~=~ \frac{1}{|x^*|}.$$ $\sum_{s\ni e} x^*_s \ge 1$$e$$|p^t| = 1$$1/|x^*|$, granica żalu oznacza Zgodnie z definicją mamy (każda runda wybiera jeden zestaw), a , dając Zatrzymujemy proces, gdy , więc wtedy (przestawienie warunków) To znaczy, normalizacja daje co najwyżej ułamkowy zestaw wielkości czasy optymalne. $$\frac{T}{|x^*|} \le \varepsilon^{-1}\ln(m) + \min_e \sum_t a_e^t.$$ $X$$|X| = T$$\sum_t a_e^t = \sum_e [e\in s^t] = \sum_{s\ni e} X_s$ $$\frac{|X|}{|x^*|} \le \varepsilon^{-1}\ln(m) +\min_e \sum_{s\ni e} X_s.$$ $\min_e \sum_{s\ni e} X_s = \Omega(\varepsilon^{-2}\ln m)$ $$\frac{|X|}{\min_e \sum_{s\ni e} X_s}~ \le~ (1+O(\varepsilon)|x^*|.$$ $X$$(1+O(\varepsilon))$

Uwaga: W pewnym sensie ta interpretacja teorii uczenia się uogólnia interpretację algorytmiczną. Jednak niektóre techniki algorytmiczne niezbędne dla wydajności (takie jak nierównomierne przyrosty i pomijanie spełnionych ograniczeń pokrycia) nie wydają się naturalnie przenosić się na teorię uczenia się. Podobnie, algorytmy mieszanego pakowania i pokrywania płyt LP (np. Te ) nie wydają się mieć naturalnych analogów w ustawieniach teorii uczenia się.