Menyortir sebagai program linier

Sejumlah masalah mengejutkan memiliki pengurangan yang cukup alami untuk pemrograman linier (LP). Lihat Bab 7 dari [1] untuk contoh-contoh seperti aliran jaringan, pencocokan bipartit, permainan zero-sum, jalur terpendek, bentuk regresi linier, dan bahkan evaluasi sirkuit!

Karena evaluasi rangkaian dikurangi menjadi pemrograman linier, setiap masalah dalam harus memiliki formulasi pemrograman linier. Oleh karena itu, kami memiliki algoritme pengurutan "baru", melalui reduksi ke program linier. Jadi, pertanyaan saya adalah$P$

1. Apa program linier yang akan mengurutkan array bilangan real?$n$
2. Berapa waktu berjalan algoritma sorting yang dikurangi ke LP dan pecahkan?

1. Algoritma oleh S. Dasgupta, C. Papadimitriou dan U. Vazirani (2006)

Jawaban berikut pada dasarnya setara dengan jawaban yang sudah Anda ketahui, tetapi mungkin tampak sedikit kurang "ajaib". Di sisi lain, ini lebih teknis, tetapi saya percaya teknik umum "menulis masalah Anda sebagai optimasi pada matriks permutasi dan memanggil Birkhoff-von Neumann" adalah teknik yang hebat untuk diketahui.

Untuk permutasi dari { 1 , … , n } mendefinisikan permutasi matriks P σ sebagai matriks 0-1 sehingga P i j = 1 jika j = σ ( i ) dan P i j = 0 sebaliknya. Ini hanyalah matriks yang memungkinkan koordinat vektor x menurut σ : jika y = P σ x maka y i = x $\sigma$$\{1, \ldots, n\}$$P_\sigma$$P_{ij} = 1$$j = \sigma(i)$$P_{ij}=0$$x$$\sigma$$y = P_\sigma x$ . Saya akan menyatakany= P σ xsebagaiσ(x)mulai sekarang.$y_i = x_{\sigma(i)}$$y=P_{\sigma}x$$\sigma(x)$

Satu definisi yang lebih: non-negatif matriks M adalah ganda-stokastik jika masing-masing baris dan masing-masing dari jumlah kolom untuk 1.$n\times n$$M$

Dan satu fakta yang sangat penting dalam optimasi kombinatorial - teorema Birkhoff-von Neumann:

Sebuah matriks adalah stokastik ganda jika dan hanya jika itu adalah kombinasi cembung matriks permutasi, yaitu jika dan hanya jika terdapat permutasi σ 1 , ... , σ k dan real positif a 1 , ... , α k sehingga M = Σ k i = 1 α i P σ i dan ∑ α 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$

Perhatikan bahwa matriks stochastic ganda didefinisikan oleh ketidaksetaraan

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

Semua ketidaksetaraan ini secara bersama-sama menentukan polytope , dan teorema Birkhoff-von Neumann menyatakan bahwa titik-titik ekstrem (simpul) dari polytope ini adalah semua matriks permutasi. Dari pemrograman linear dasar, kita tahu ini menyiratkan bahwa setiap program linear yang memiliki ketidaksetaraan di atas sebagai kendala (dan tidak ada kendala lain) akan memiliki matriks permutasi sebagai solusi optimal.$P$

Jadi diberi input untuk disortir, kita hanya perlu membuat tujuan linier f a ( M ) yang:$a = (a_1, \ldots, a_n)$$f_a(M)$

• jika σ ( a ) diurutkan tetapi τ ( a ) tidak.$f_a(P_\tau) < f_a(P_\sigma)$$\sigma(a)$$\tau(a)$

Kemudian merumuskan program linier dengan tujuan untuk memaksimalkan dan ketidaksetaraan di atas sebagai kendala, dan Anda dijamin bahwa solusi optimal adalah matriks permutasi P σ untuk σ sehingga σ ( a ) diurutkan. Tentu saja, mudah untuk "membacakan" σ dari P σ .$f_a(M)$$P_\sigma$$\sigma$$\sigma(a)$$\sigma$$P_\sigma$

Satu pilihan untuk adalah v T M a di mana v = ( 1 , … , n ) . Verifikasi itu$f_a(M)$$v^T M a$$v = (1, \ldots, n)$

• ini linear dalam ;$M$
• untuk , f a ( P σ ) = ∑ n i = 1 i a σ ( i ) ;$P_\sigma$$f_a(P_\sigma) = \sum_{i = 1}^n{i a_{\sigma(i)}}$
• $\sigma$$\sigma(a)$$\sigma(a)$

Dan voila, Anda memiliki program linear untuk menyortir. Tampaknya konyol untuk menyortir, tetapi ini sebenarnya metode yang ampuh dalam optimasi.