Tri en tant que programme linéaire

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

Puisque l'évaluation du circuit se réduit à une programmation linéaire, tout problème dans $P$ doit avoir une formulation de programmation linéaire. Par conséquent, nous avons un "nouvel" algorithme de tri, via 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. Quel est le temps d'exécution de l'algorithme de tri de réduction en LP et de résolution?

1. Algorithmes de S. Dasgupta, C. Papadimitriou et U. Vazirani (2006)

La réponse suivante est fondamentalement équivalente à celle que vous connaissez déjà, mais peut sembler un peu moins "magique". D'un autre côté, c'est plus technique, mais je pense que la technique générale "écrire votre problème comme une optimisation sur les matrices de permutation et invoquer Birkhoff-von Neumann" est une bonne méthode à connaître.

Pour une permutation de { 1 , … , n }, définissez la matrice de permutation P σ comme la matrice 0-1 telle que P i j = 1 si j = σ ( i ) et P i j = 0 sinon. C'est simplement la matrice qui permute les coordonnées d'un vecteur x selon σ : si y = P σ x alors y i = x $\sigma$$\{1, \ldots, n\}$$P_\sigma$$P_{ij} = 1$$j = \sigma(i)$$P_{ij}=0$$x$$\sigma$$y = P_\sigma x$ . Je dénoterai$y_i = x_{\sigma(i)}$ que σ ( x ) à partirmaintenant.$y=P_{\sigma}x$$\sigma(x)$

Encore une définition: une matrice non négative M est doublement stochastique si chacune de ses lignes et chacune de ses colonnes totalisent 1.$n\times n$$M$

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

Une matrice est doublement stochastique si et seulement si elle est une combinaison convexe de matrices de permutation, c'est-à-dire si et seulement s'il existe des permutations σ 1 , … , σ k et des réels positifs α 1 , … , α k tels que M = ∑ k i = 1 α i P σ i et ∑ α i = 1 .$M$$\sigma_1, \ldots, \sigma_k$$\alpha_1 , \ldots, \alpha_k$$M = \sum_{i = 1}^k{\alpha_i P_{\sigma_i}}$$\sum{\alpha_i} = 1$

Notez qu'une matrice doublement stochastique est définie par les inégalités

∀ j : n ∑ i = 1 M i j = 1 ∀ i , j : M i j ≥

Toutes ces inégalités prises ensemble déterminent un polytope $P$

$a = (a_1, \ldots, a_n)$$f_a(M)$ pour lequel:

• $f_a(P_\tau) < f_a(P_\sigma)$$\sigma(a)$$\tau(a)$ ne l'est pas.

$f_a(M)$$P_\sigma$$\sigma$$\sigma(a)$$\sigma$$P_\sigma$ .

$f_a(M)$$v^T M a$$v = (1, \ldots, n)$

• $M$
• $P_\sigma$$f_a(P_\sigma) = \sum_{i = 1}^n{i a_{\sigma(i)}}$
• $\sigma$$\sigma(a)$$\sigma(a)$

Et voila, vous avez un programme linéaire de tri. Semble idiot pour le tri, mais c'est en fait une méthode puissante d'optimisation.