線形プログラムとしてのソート

Question

驚くべき数の問題は、線形プログラミング（LP）に対してかなり自然な減少をもたらします。見る 第7章 1]、ネットワークフロー、二部マッチング、ゼロサムゲーム、最短パス、線形回帰の形態、さらには回路評価などの例については[1]。

回路評価は線形プログラミングに減少するため、$ P $の問題には線形プログラミングの定式化が必要です。したがって、線形プログラムへの削減により、「新しい」ソートアルゴリズムがあります。だから、私の質問はそうです

1. $ n $の実数の配列をソートする線形プログラムは何ですか？
2. redoce-and-solveソーティングアルゴリズムの実行時間は何ですか？

---

1. アルゴリズム S. Dasgupta、C。papadimitriouおよびU. Vazirani（2006）

Answer 1

次の答えは、基本的にあなたがすでに知っているものと同等ですが、「魔法のような」ほど少ないように見えるかもしれません。一方、それはより技術的ですが、一般的な手法は「あなたの問題を順列行列の最適化として書いて、Birkhoff-von Neumannを呼び出す」ことは素晴らしいものだと思います。

$ {1、 ldots、n } $の順列$ sigma $の場合、$ p_ {ij} = 1 $ if if if if j = のように、順列行列$ p_ sigma $を0-1マトリックスとして定義します。 sigma（i）$ and $ p_ {ij} = 0 $それ以外の場合。これは、単に$ sigma $：if $ y = p_ sigma x $ then $ y_i = x _ { sigma（i）} $に従って、ベクトル$ x $の座標に焦点を当てるマトリックスです。私は$ y = p _ { sigma} x $を$ sigma（x）$ as on from on on on on onに示します。

もう1つの定義：非陰性$ n times n $ matrix $ m $は、その行のそれぞれとその列のそれぞれが1に合計されている場合、二重に確率的です。

そして、組み合わせの最適化において非常に重要な1つの事実 - Birkhoff -Von Neumann定理：

マトリックス$ m $は、順列行列の凸の組み合わせである場合のみ、つまり存在する場合にのみ、二重に確率的です。アルファ_k$ $ m = sum_ {i = 1}^k { alpha_i p _ { sigma_i}} $および$ sum { alpha_i} = 1 $。

二重に確率的行列は不平等によって定義されていることに注意してください

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

これらの不平等はすべて、ポリトープ$ p $を決定し、Birkhoff-von Neumann定理は、このポリトープの極端な点（頂点）がすべて順列行列であると述べています。基本的な線形プログラミングから、これは、その制約として上記の不平等を持つ線形プログラム（および他の制約）が最適な解として順列行列を持つことを意味することを意味します。

したがって、入力$ a =（a_1、 ldots、a_n）$を並べ替えると、線形目的$ f_a（m）$を考え出す必要があります。

• $ f_a（p_ tau）<f_a（p_ sigma）$ $ sigma（a）$がソートされますが、$ tau（a）$はそうではありません。

次に、$ f_a（m）$を最大化するための目的で線形プログラムを策定し、上記の不平等を制約として最大化すると、最適なソリューションが$ sigma（ a）$はソートされます。もちろん、$ p_ sigma $から$ sigma $を「読み取る」のは簡単です。

$ f_a（m）$の1つの選択肢は$ v^tm 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）$の2つの座標を切り替えて、より高い値を達成できます）。

そして、出来上がり、ソートのための線形プログラムがあります。並べ替えはばかげているように見えますが、これは実際には最適化における強力な方法です。