Sortowanie jako program liniowy

24

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)
Joe
źródło
3
Jeśli znasz już odpowiedź, dlaczego zadajesz pytanie?
Yuval Filmus
2
@Joe Publikowanie interesujących materiałów jest w porządku, nawet jeśli znasz odpowiedź. Konwencjonalnym sposobem na to jest udzielenie odpowiedzi na własne pytanie (wyszukanym) ujęciem (zamiast zamieszczania linków do niektórych dokumentów, które mogą się zepsuć).
Raphael
@ Rafael Jeśli nikt inny nie napisze odpowiedzi, zrobię to, kiedy będę miał czas.
Joe
@YuvalFilmus zadaje pytanie, na które znasz odpowiedź, jest wyraźnie zalecane przy wymianie stosu .
Joe

Odpowiedzi:

23

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 )σ{1,,n}PσPij=1j=σ(i)Pij=0xσy=Pσxyi=xσ(i)y=Pσxσ(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.M.n×nM

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 = 1Mσ1,,σkα1,,αkM=i=1kαiPσiαi=1

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

i:j=1nMij=1
j:i=1nMij=1
i,j:Mij0

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=(a1,,an)fa(M)

  • fa(Pτ)<fa(Pσ) jeśli jest posortowane, ale nie jest.σ(a)τ(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 .fa(M)Pσσσ(a)σPσ

Jednym wyborem dla jest gdzie . Zweryfikuj tofa(M)vTMav=(1,,n)

  • jest to liniowe w ;M
  • dla , ;f a ( P σ ) = n i = 1 i a σ ( i )Pσfa(Pσ)=i=1niaσ(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 )σσ(a)σ(a)

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

Sasho Nikolov
źródło
1
Coś, z czym nie miałem do czynienia: gdy istnieje wiele optymalnych rozwiązań, niektóre z nich nie będą macierzami permutacji (a niektóre oczywiście będą). Istnieje wiele łatwych sposobów, aby to naprawić: przez zaburzenie możesz usunąć duplikaty w . a
Sasho Nikolov
1
Gdy istnieje wiele optymalnych rozwiązań, niektóre mogą nie być macierzami permutacji (ale zawsze pewne optymalne rozwiązanie będzie macierzą permutacji). Jeśli funkcja celu jest stała, wszystkie możliwe rozwiązania są optymalne.
Sasho Nikolov,
1
@ Turbo program liniowy jest w całości napisany w tej odpowiedzi. Oczywiście nie ma ograniczeń integralności. Nie zamierzam odpowiadać na twoje drugie pytanie. Usiądź i spróbuj zapisać GI jako optymalizację funkcji liniowej na podwójnie stochastycznych matrycach, tak jak tutaj zrobiłem dla sortowania. Przekonaj się, gdzie się nie powiedzie.
Sasho Nikolov,
1
W praktyce prawdopodobnie będziesz chciał zastosować simpleks, ale teoretycznie możesz uzyskać algorytm wielomianu czasu za pomocą solwera LP z wielomianem czasu, na przykład metodą punktu wewnętrznego lub metodą elipsoidy. To daje czas wielomian w złożoności bitowej . Gdy macierzą ograniczeń jest TUM (jak ma to miejsce w tym przypadku), istnieją silnie rozwiązywacze czasu polytime zbyt cstheory.stackexchange.com/questions/4454/… . a
Sasho Nikolov
1
I tak, najłatwiejszą rzeczą do zrobienia jest, aby upewnić się, że unikalne rozwiązanie optymalne, co można zrobić dodając niewielką losową perturbacji do . a
Sasho Nikolov