Ordenar como un programa lineal

24

Un sorprendente número de problemas tiene reducciones bastante naturales a la programación lineal (LP). Consulte el Capítulo 7 de [1] para ver ejemplos como flujos de red, emparejamiento bipartito, juegos de suma cero, rutas más cortas, una forma de regresión lineal e incluso evaluación de circuitos.

Dado que la evaluación del circuito se reduce a la programación lineal, cualquier problema en P debe tener una formulación de programación lineal. Por lo tanto, tenemos un "nuevo" algoritmo de clasificación, mediante reducción a un programa lineal. Entonces, mis preguntas son

  1. ¿Cuál es el programa lineal que clasificará una matriz de n números reales?
  2. ¿Cuál es el tiempo de ejecución del algoritmo de clasificación de reducir a LP y resolver?

  1. Algoritmos de S. Dasgupta, C. Papadimitriou y U. Vazirani (2006)
Joe
fuente
3
Si ya sabe la respuesta, ¿por qué hace la pregunta?
Yuval Filmus
2
@ Joe Está bien publicar material interesante incluso si sabes la respuesta. La forma convencional de hacerlo es responder su propia pregunta con una toma (elaborada) (en lugar de publicar enlaces a algún documento, que puede romperse).
Raphael
@Raphael Si nadie más escribe una respuesta, lo haré cuando tenga tiempo.
Joe
@YuvalFilmus haciendo una pregunta que ya sabe la respuesta a está animado de forma explícita en el intercambio de pila .
Joe

Respuestas:

23

La siguiente respuesta es básicamente equivalente a la que ya conoce, pero puede parecer un poco menos "mágica". Por otro lado, es más técnico, pero creo que la técnica general "escribir su problema como una optimización en matrices de permutación e invocar a Birkhoff-von Neumann" es excelente.

Para una permutación de { 1 , ... , n } defina la matriz de permutación P σ como la matriz 0-1 de modo que P i j = 1 si j = σ ( i ) y P i j = 0 de lo contrario. Esta es simplemente la matriz que permuta las coordenadas de un vector x de acuerdo con σ : si y = P σ x entonces y i = x σσ{1,,n}PσPij=1j=σ(i)Pij=0xσy=Pσxyi=xσ(i) . Denotaré como σ ( x ) de ahora en adelante.y=Pσxσ(x)

Una definición más: una matriz no negativa M es doblemente estocástica si cada una de sus filas y cada una de sus columnas suma 1.n×nM

Y un hecho que es muy importante en la optimización combinatoria: el teorema de Birkhoff-von Neumann:

Una matriz es doblemente estocástica si y solo si es una combinación convexa de matrices de permutación, es decir, si y solo si existen permutaciones σ 1 , ... , σ k y reales positivos α 1 , ... , α k tal que M = k i = 1 α i P σ i y α i = 1 .Mσ1,,σkα1,,αkM=i=1kαiPσiαi=1

Observe que una matriz doblemente estocástica está definida por las desigualdades

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

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

Todas estas desigualdades tomadas juntas determinan un politopo , y el teorema de Birkhoff-von Neumann establece que los puntos extremos (vértices) de este politopo son todas matrices de permutación. Por programación lineal básica, sabemos que esto implica que cualquier programa lineal que tenga las desigualdades anteriores como sus restricciones (y ninguna otra restricción) tendrá una matriz de permutación como una solución óptima.P

Entonces, dada una entrada para ser ordenada, solo tenemos que llegar a un objetivo lineal f a ( M ) para el cual:a=(a1,,an)fa(M)

  • fa(Pτ)<fa(Pσ)σ(a)τ(a) no lo está.

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

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

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

Y listo, tienes un programa lineal para ordenar. Parece una tontería clasificar, pero este es de hecho un método poderoso en la optimización.

Sasho Nikolov
fuente
1
una
1
Cuando hay múltiples soluciones óptimas, algunas pueden no ser matrices de permutación (pero siempre alguna solución óptima será una matriz de permutación). Si la función objetivo es constante, todas las soluciones viables son óptimas.
Sasho Nikolov
1
@Turbo, el programa lineal está completamente escrito en esta respuesta. Obviamente no tiene restricciones de integralidad. No voy a intentar responder tu segunda pregunta. Siéntese e intente escribir GI como optimización de una función lineal sobre matrices doblemente estocásticas, como lo he hecho aquí para ordenar. Mira por ti mismo dónde falla.
Sasho Nikolov
1
a
1
a