Sortowanie jako program liniowy

Zaskakująca liczba problemów ma dość naturalne ograniczenia w programowaniu liniowym (LP). Przykłady, takie jak przepływy sieciowe, dopasowanie dwustronne, gry o sumie zerowej, najkrótsze ścieżki, forma regresji liniowej, a nawet ocena obwodu, patrz rozdział 7 w [1]!

Ponieważ ocena obwodu ogranicza się do programowania liniowego, każdy problem w musi mieć sformułowanie programowania liniowego. Dlatego mamy „nowy” algorytm sortowania poprzez redukcję do programu liniowego. Więc moje pytania są$P$

1. Jaki jest program liniowy, który posortuje tablicę liczb rzeczywistych?$n$
2. Jaki jest czas działania algorytmu sortowania redukcji do LP i rozwiązania?

1. Algorytmy S. Dasgupta, C. Papadimitriou i U. Vazirani (2006)

Poniższa odpowiedź jest w zasadzie równoważna tej, którą już znasz, ale może wydawać się nieco mniej „magiczna”. Z drugiej strony jest bardziej techniczna, ale uważam, że ogólna technika „napisz swój problem jako optymalizacja macierzy permutacji i wywołaj Birkhoffa-von Neumanna” jest świetna do poznania.

Dla permutacji z zdefiniuj macierz permutacji jako macierz 0-1, tak że jeśli i przeciwnym razie. Jest to po prostu macierz, która permutuje współrzędne wektora zgodnie z : jeśli to . Odtąd oznaczę jako .{ 1 , … , n } P σ P i j = 1 j = σ ( i ) P i j = 0 x σ y = P σ x y i = x σ ( i ) y = P σ x σ ( x $\sigma$$\{1, \ldots, n\}$$P_\sigma$$P_{ij} = 1$$j = \sigma(i)$$P_{ij}=0$$x$$\sigma$$y = P_\sigma x$$y_i = x_{\sigma(i)}$$y=P_{\sigma}x$$\sigma(x)$

Jeszcze jedna definicja: nieujemna macierz jest podwójnie stochastyczna, jeśli każdy z jej wierszy i każda z kolumn sumuje się do 1.$n\times n$$M$

I jeden fakt, który jest bardzo ważny w optymalizacji kombinatorycznej - twierdzenie Birkhoffa-von Neumanna:

Macierz jest podwójnie stochastyczna wtedy i tylko wtedy, gdy jest wypukłą kombinacją macierzy permutacji, tj. i tylko wtedy, gdy istnieją permutacje i dodatnie reals takie, że i .σ 1 , … , σ k α 1 , … , α k M = ∑ k i = 1 α i P σ i ∑ α i = $M$$\sigma_1, \ldots, \sigma_k$$\alpha_1 , \ldots, \alpha_k$$M = \sum_{i = 1}^k{\alpha_i P_{\sigma_i}}$$\sum{\alpha_i} = 1$

Zauważ, że podwójnie stochastyczna matryca jest definiowana przez nierówności

Wszystkie te nierówności wzięte razem determinują polytop , a twierdzenie Birkhoffa-von Neumanna stwierdza, że ​​wszystkie krańcowe punkty (wierzchołki) tego polytopa są macierzami permutacji. Z podstawowego programowania liniowego wiemy, że oznacza to, że każdy program liniowy, który ma powyższe nierówności jako swoje ograniczenia (i żadnych innych ograniczeń), będzie miał macierz permutacji jako optymalne rozwiązanie.$P$

Zatem biorąc pod uwagę dane wejściowe do posortowania, musimy tylko opracować liniowy cel dla którego:$a = (a_1, \ldots, a_n)$$f_a(M)$

• $f_a(P_\tau) < f_a(P_\sigma)$ jeśli jest posortowane, ale nie jest.$\sigma(a)$$\tau(a)$

Następnie sformułuj program liniowy w celu maksymalizacji i powyższych nierówności jako ograniczeń, a masz gwarancję, że optymalnym rozwiązaniem jest macierz permutacji dla tak że jest sortowane. Oczywiście łatwo jest „odczytać” z .$f_a(M)$$P_\sigma$$\sigma$$\sigma(a)$$\sigma$$P_\sigma$

Jednym wyborem dla jest gdzie . Zweryfikuj to$f_a(M)$$v^T M a$$v = (1, \ldots, n)$

• jest to liniowe w ;$M$
• dla , ;f a ( P σ ) = ∑ n i = 1 i a σ ( i $P_\sigma$$f_a(P_\sigma) = \sum_{i = 1}^n{i a_{\sigma(i)}}$
• powyższe jest zmaksymalizowane przy dla którego sortowana jest (sprzecznie: w przeciwnym razie możesz zmienić dwie współrzędne i osiągnąć wyższą wartość).σ ( a ) σ ( a $\sigma$$\sigma(a)$$\sigma(a)$

I voila, masz liniowy program do sortowania. Wydaje się głupie do sortowania, ale w rzeczywistości jest to skuteczna metoda optymalizacji.