Sortierung als lineares Programm

24

Eine überraschende Anzahl von Problemen hat eine ziemlich natürliche Reduktion auf die lineare Programmierung (LP). In Kapitel 7 von [1] finden Sie Beispiele für Netzwerkflüsse, bipartite Matching, Nullsummenspiele, kürzeste Pfade, eine Form der linearen Regression und sogar die Auswertung von Schaltkreisen!

Da sich die Schaltungsbewertung auf lineare Programmierung reduziert, muss jedes Problem in eine lineare Programmierformulierung haben. Daher haben wir einen "neuen" Sortieralgorithmus, der auf ein lineares Programm reduziert wird. Also meine Fragen sindP

  1. Was ist das lineare Programm, das ein Array von reellen Zahlen sortiert ?n
  2. Welche Laufzeit hat der Sortieralgorithmus zum Reduzieren auf LP und zum Lösen?

  1. Algorithmen von S. Dasgupta, C. Papadimitriou und U. Vazirani (2006)
Joe
quelle
3
Wenn Sie die Antwort bereits kennen, warum stellen Sie die Frage?
Yuval Filmus
2
@ Joe Es ist in Ordnung, interessantes Material zu posten, auch wenn Sie die Antwort kennen. Die konventionelle Art, dies zu tun, besteht darin, Ihre eigene Frage mit einer (aufwändigen) Antwort zu beantworten (anstatt Links zu einem Dokument zu veröffentlichen, die möglicherweise nicht mehr funktionieren).
Raphael
@Raphael Wenn sonst niemand eine Antwort schreibt, dann werde ich, wenn ich Zeit habe.
Joe
@YuvalFilmus, der eine Frage stellt, auf die Sie die Antwort wissen, wird ausdrücklich beim Stapelaustausch empfohlen .
Joe

Antworten:

23

Die folgende Antwort entspricht im Wesentlichen der, die Sie bereits kennen, scheint jedoch etwas weniger "magisch" zu sein. Auf der anderen Seite ist es technischer, aber ich glaube, dass die allgemeine Technik "Schreiben Sie Ihr Problem als Optimierung für Permutationsmatrizen und rufen Sie Birkhoff-von Neumann auf" eine großartige Technik ist.

Für eine Permutation von { 1 , ... , n } definiert die Permutationsmatrix P σ als die 0-1 - Matrix derart , daß P i j = 1 , wenn j = σ ( i ) und P i j = 0 sonst. Dies ist einfach die Matrix, die die Koordinaten eines Vektors x gemäß σ permutiert : Wenn y = P σ x, dann ist y i = x σσ{1,,n}PσPij=1j=σ(i)Pij=0xσy=Pσx . Ich werdevon nun any= P σ xalsσ(x) bezeichnen.yi=xσ(i)y=Pσxσ(x)

Noch eine Definition: Eine nicht negative Matrix M ist doppelt stochastisch, wenn jede ihrer Zeilen und jede ihrer Spalten zu 1 summiert.n×nM

Und eine Tatsache, die für die kombinatorische Optimierung sehr wichtig ist - das Birkhoff-von-Neumann-Theorem:

Eine Matrix ist genau dann doppelt stochastisch, wenn es sich um eine konvexe Kombination von Permutationsmatrizen handelt, dh wenn Permutationen σ 1 , , σ k und positive Reelle α 1 , , α k existieren, so dass M = k i = 1 α i P σ i und α i = 1 .Mσ1,,σkα1,,αkM=i=1kαiPσiαi=1

Beachten Sie, dass eine doppelt stochastische Matrix durch die Ungleichungen definiert wird

j : n Σ i = 1 M i j = 1 i , j : M i j0

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

Alle diese Ungleichungen zusammen ergeben ein Polytop , und das Birkhoff-von-Neumann-Theorem besagt, dass die Extrempunkte (Eckpunkte) dieses Polytops alle Permutationsmatrizen sind. Aus der linearen Grundprogrammierung wissen wir, dass jedes lineare Programm, das die obigen Ungleichungen als Nebenbedingungen (und keine anderen Nebenbedingungen) aufweist, eine Permutationsmatrix als optimale Lösung hat.P

Wenn also eine Eingabe sortiert werden soll, müssen wir nur ein lineares Objektiv f a ( M ) aufstellen, für das:a=(a1,,an)fa(M)

  • fa(Pτ)<fa(Pσ)σ(a)τ(a)

fa(M)Pσσσ(a)σPσ

fa(M)vTMav=(1,,n)

  • M
  • Pσfa(Pσ)=i=1niaσ(i)
  • σσ(a)σ(a)

Und voila, du hast ein lineares Programm zum Sortieren. Scheint albern für das Sortieren, aber dies ist in der Tat eine leistungsfähige Methode zur Optimierung.

Sasho Nikolov
quelle
1
a
1
Wenn es mehrere optimale Lösungen gibt, sind einige möglicherweise keine Permutationsmatrizen (aber immer ist eine optimale Lösung eine Permutationsmatrix). Wenn die Zielfunktion konstant ist, sind alle möglichen Lösungen optimal.
Sasho Nikolov
1
@Turbo das lineare Programm ist vollständig in dieser Antwort geschrieben. Offensichtlich gibt es keine Integritätsbeschränkungen. Ich werde nicht versuchen, Ihre zweite Frage zu beantworten. Setzen Sie sich und versuchen Sie, GI so aufzuschreiben, dass es eine lineare Funktion über doppelt stochastische Matrizen optimiert, wie ich es hier für die Sortierung getan habe. Überzeugen Sie sich selbst, wo es versagt.
Sasho Nikolov
1
a
1
a