Tri comme un programme linéaire

Question

Un nombre surprenant de problèmes ont des réductions assez naturelles à la programmation linéaire (LP). Voir Chapitre 7 de [1] pour des exemples tels que les flux de réseau, correspondant bipartite, jeux à somme nulle, les plus courts chemins, une forme de régression linéaire, et même de l'évaluation du circuit!

Depuis l'évaluation du circuit réduit à la programmation linéaire, tout problème en $ P $ doit avoir une formulation de programmation linéaire. Par conséquent, nous avons un « nouveau » algorithme de tri, par la réduction à un programme linéaire. Donc, mes questions sont

1. Quel est le programme linéaire qui triera un tableau de $ n $ nombres réels?
2. Quelle est la durée de la réduire à LP-et résoudre algorithme de tri?

---

1. algorithmes par S. Dasgupta, C. Papadimitriou et U. Vazirani ( 2006)

Answer 1

La réponse suivante est essentiellement équivalente à celle que vous connaissez déjà, mais peut sembler un peu moins « magique ». D'autre part, il est plus technique, mais je crois que la technique générale « écrire votre problème comme une optimisation sur des matrices de permutation et Invoke Birkhoff-von Neumann » est un grand savoir.

Pour une permutation $ \ sigma $ de $ \ {1, \ ldots, n \} $ définir la matrice permutation $ P_ \ sigma $ que la matrice 0-1 de telle sorte que $ P_ {ij} = 1 $ si $ j = \ sigma (i) $ et $ P_ {} = ij de 0 $ autrement. Ceci est simplement la matrice qui permute les coordonnées d'un $ vectoriel x $ selon \ $ sigma $: si $ y = P_ \ sigma x $, alors $ y_i = x _ {\ sigma (i)} $. Je vais y = $ désignent P _ {\ sigma} x $ comme $ \ sigma (x) $ désormais.

Une définition plus:. $ Un non-négatif n \ n fois $ matrice $ M $ est doublement stochastique si chacune de ses lignes et chacune de ses colonnes sommes à 1

Et un fait qui est très important dans l'optimisation combinatoire - le théorème Neumann Birkhoff-von:

  

Une matrice $ M $ est doublement stochastique si et seulement si elle est une combinaison convexe de matrices de permutation, à savoir si et seulement s'il existe des permutations $ \ sigma_1, \ ldots, \ sigma_k $ et réels positifs $ \ alpha_1, \ ldots, \ alpha_k $ tel que $ M = \ {sum_ i = 1} ^ k {\ alpha_i P _ {\ sigma_i}} $ et somme \ $ {\ alpha_i} = 1 $.

Notez que la matrice doublement stochastique est défini par les inégalités

$$ \ 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 $$

Toutes ces inégalités pris ensemble déterminer un polytope $ P $ et le Neumann Birkhoff-von théorème indique que les points extrémaux (sommets) de ce polytope sont toutes les matrices de permutation. De la programmation linéaire de base, nous savons que cela implique que tout programme linéaire qui a les inégalités ci-dessus comme ses contraintes (et pas d'autres contraintes) aura une matrice de permutation comme une solution optimale.

donné une entrée $ a = (A_1, \ ldots, a_n) $ à trier, nous avons juste besoin de trouver un objectif linéaire f_a de $ (M) $ pour lesquels:

• $ f_a (P_ \ tau)

Ensuite, formuler un programme linéaire avec l'objectif de maximiser $ f_a (M) $ et les inégalités ci-dessus que les contraintes, et vous êtes assuré qu'une solution optimale est la matrice permutation $ P_ \ sigma $ pour $ \ sigma $ tel que $ \ sigma (a) $ est trié. Bien sûr, il est facile de "lire off" $ \ sigma $ de $ P_ de sigma de $.

Un choix pour $ f_a (M) est $ v ^ T M $ a $ où v = (1, \ ldots, n) $. Vérifiez que

• c'est linéaire $ M $;
• pour $ P_ de $ de sigma, $ f_a (P_ \ sigma) = \ {sum_ i = 1} ^ n {i a _ {\ sigma (i)}} $;
• ce qui précède est maximisée au $ \ sigma $ pour lequel $ \ sigma (a) $ est trié (par contradiction: sinon vous pouvez passer deux coordonnées de $ \ sigma (a) $ et d'atteindre une valeur plus élevée) <. / li>

Et le tour est joué, vous avez un programme linéaire pour le tri. Semble idiot pour le tri, mais cela est en fait une méthode puissante dans l'optimisation.