Ordenando como un programa lineal

Question

Un sorprendente número de problemas tienen reducciones bastante naturales a la programación lineal (LP). Ver Capítulo 7 de [1] para los ejemplos como los flujos de red, coincidente bipartita, juegos de suma cero, los caminos más cortos, una forma de regresión lineal, y la evaluación de circuito, incluso!

Desde Evaluación circuito reduce a la programación lineal, cualquier problema en $ P $ debe tener una formulación de programación lineal. Por lo tanto, tenemos una "nueva" algoritmo de ordenación, a través de la reducción a un programa lineal. Por lo tanto, mis preguntas son

1. ¿Cuál es el programa lineal que ordenar un arreglo de $ n $ números reales?
2. ¿Cuál es el tiempo de funcionamiento del reducir-a-LP-y-solucionar algoritmo de ordenación?

---

1. Algoritmos por S. Dasgupta, C. Papadimitriou y U. Vazirani ( 2006)

Answer 1

La siguiente respuesta es básicamente equivalente a la que ya se sabe, 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 y la invocación de Birkhoff-Von Neumann" es un gran uno a saber.

Para una permutación $ \ sigma $ de $ \ {1, \ ldots, n \} $ definir la permutación matriz $ P_ \ sigma $ como el 0-1 matriz tal que $ P_ {ij} = 1 $ si $ j = \ sigma (i) $ y $ P_ {ij} $ = 0 de otro modo. Esto es simplemente la matriz que permuta las coordenadas de un vector $ x $ de acuerdo con $ \ sigma $: si $ y = P_ \ sigma x $ entonces $ y_i = x _ {\ sigma (i)} $. Voy a denotar $ y = P _ {\ sigma} x $ como $ \ sigma (x) $ a partir de ahora.

Una definición más:. Un $ no negativo n \ veces n $ matriz $ M $ es doblemente estocástica si cada uno de sus filas y cada una de sus columnas sumas para 1

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

Una matriz $ M $ es doblemente estocástica si y sólo si es una combinación convexa de matrices de permutación, es decir, si y sólo si existen permutaciones $ \ sigma_1, \ ldots, \ sigma_k $ y reales positivos $ \ alpha_1, \ ldots, \ alpha_k $ tal que $ M = \ sum_ {i = 1} ^ k {\ alpha_i P _ {\ sigma_i}} $ y $ \ sum {\ alpha_i} = 1 $.

Tenga en cuenta que una matriz doblemente estocástica se define por las desigualdades

$$ \ forall i: \ sum_ {j = 1} ^ n {M_ {ij}} = 1 $$ $$ \ forall j: \ sum_ {i = 1} ^ n {M_ {ij}} = 1 $$ $$ \ forall i, j: M_ {ij} \ geq 0 $$

Todas estas desigualdades tomados juntos determinar un politopo $ P $, y la Birkhoff-von Neumann teorema afirma que los puntos extremales (vértices) de este politopo son todas las matrices de permutación. A partir de la programación lineal básica, sabemos que esto implica que cualquier programa lineal que tiene las desigualdades anteriores como sus limitaciones (y no hay otras restricciones) tendrá una matriz de permutación como una solución óptima.

Así que dada una entrada $ a = (a_1, \ ldots, a_n) $ que ser resuelto, sólo tenemos que llegar a una lineal $ f_a objetivo (M) $ para los que:

• $ f_a (P_ \ tau)

A continuación, la formulación de un programa lineal con el objetivo de maximizar $ f_a (M) $ y las desigualdades anteriores como las limitaciones, y se le garantiza que una solución óptima es la permutación de la matriz $ P_ \ sigma $ por $ \ sigma $ tal que $ \ sigma (a) $ está ordenada. Por supuesto, es fácil de "leer off" $ \ sigma $ de $ P_ \ sigma $.

Una opción para $ f_a (M) $ es $ v ^ T M A $ donde $ v = (1, \ ldots, n) $. Verificar que

• Este es lineal en $ M $;
• por $ P_ \ sigma $, $ f_a (P_ \ sigma) = \ sum_ {i = 1} ^ {n i a _ {\ sigma (i)}} $;
• lo anterior se maximiza en la $ \ sigma $ para el que (a) $ se ordena $ \ sigma (por contradicción: de lo contrario podría cambiar dos coordenadas de $ \ sigma (a) $ y alcanzar un valor más alto) <. / li>

Y voila, usted tiene un programa lineal para la clasificación. Parece tonto para clasificar, pero esto es en realidad un poderoso método de optimización.