Algoritma waktu pseudo-polinomial yang lebih cepat untuk PARTITION

Saya ingin mempartisi angka yang diberikan N (mungkin atau mungkin tidak sama) menjadi 2 himpunan bagian sehingga 2 himpunan bagian memiliki jumlah sedekat mungkin dan juga kardinalitas set sama (jika n genap) atau hanya berbeda dengan 1 ( jika n aneh).

Saya pikir kita bisa melakukan ini dalam waktu polinomial semu , di mana adalah jumlah angka dalam himpunan. $O(n^2 A)$ $A$

Bisakah saya melakukan lebih baik dari ini? Yaitu, apakah ada algoritma waktu polinomial semu yang berjalan dalam waktu dengan ? $O(n^c A)$ $c < 2$

Terima kasih sebelumnya!

ds.algorithms co.combinatorics partition-problem Firebrandt
sumber

Perhatikan bahwa sebagai kasus khusus Knapsack, ia memiliki FPTAS . Lihat misalnya ELLawler. Algoritma aproksimasi cepat untuk masalah ransel .

Mathieu Chapelle

@Olexandr, maksud saya adalah apakah ada algoritma polinom pseudo yang berjalan di O (nA). maaf saya tidak dapat memposting dalam lateks.

Firebrandt

Saya takut pertanyaan ini berada di perbatasan karena terlalu sederhana. Misalnya, "Apakah masalah Partisi dengan batasan tambahan bahwa kedua set harus memiliki kardinalitas yang sama masih NP-complete?" bisa menjadi pertanyaan pekerjaan rumah yang khas dan saya takut bahwa menuliskan jawabannya mungkin berdampak negatif pada beberapa kursus dalam kompleksitas komputasi.

Tsuyoshi Ito

Bagaimana ini terlalu mendasar? Pendekatan yang jelas memberikan , dan pertanyaannya adalah apakah ada algoritma yang lebih baik berjalan dalam waktu mana . Dugaan saya adalah bahwa ini adalah pertanyaan terbuka.

O (n^{2} A)

$O(n^2A)$

O (n^{c} A)

$O(n^c A)$

c < 2

$c < 2$

Peter Shor

@ Firebrandt: Saya mengambil kebebasan mengedit pertanyaan asli Anda untuk menambahkan versi klarifikasi Anda (mengubah menjadi dengan , karena saya pikir bahkan itu mungkin pertanyaan terbuka). Jangan ragu untuk mengubahnya kembali ke jika Anda mau. Saya pikir pertanyaannya, sebagaimana diklarifikasi oleh komentar Anda, jelas tingkat penelitian.

O (n A)

$O(nA)$

O (n^{c} A)

$O(n^cA)$

c < 2

$c<2$

O (n A)

$O(nA)$

Peter Shor

Jawaban:

Seseorang dapat menyelesaikan masalah keputusan dalam waktu . $\tilde{O}(nA)$

Biarkan urutan angka menjadi . Definisikan sebagai himpunan sedemikian rupa sehingga jika jika ada dengan panjang yang berjumlah . Jika kami telah menghitung , maka kami hanya perlu waktu tambahan untuk menyelesaikan secara menyeluruh untuk menyelesaikan masalah Anda. $S$ $F_S$ $(i,j)\in F_S$ $S$ $j$ $i$ $F_S$ $O(nA)$ $F_S$

Jika dan adalah dua bagian dari partisi , maka $S_1$ $S_2$ $S$

F_{S} = F_{S_{1}} + F_{S_{2}}

$F_S = F_{S_1} + F_{S_2}$

di mana adalah jumlah minkowski, dan penambahan di antara tupel didefinisikan secara koordinat. $A+B=\{a+b | a\in A, b\in B\}$

Klaim: Menghitung dari dan membutuhkan waktu . $F_S$ $F_{S_1}$ $F_{S_2}$ $\tilde{O}(|S|A)$

Bukti: Menerapkan konvolusi 2D pada dua tabel ukuran . $A\times |S|$

Algoritma mempartisi urutan ke dua urutan berukuran sama, menerapkan rekursi untuk masing-masing, dan mengambil jumlah hasil minkowski. Misalkan menjadi waktu berjalan terburuk ketika input ke algoritma memiliki elemen dan adalah batas atas dari penjumlahan. Kami memiliki Yang menunjukkan . $T_A(n)$ $n$ $A$

T_{A} (n) = 2 T_{A} (n / 2) + A \tilde{O} (n)

$T_A(n) = 2 T_A(n/2) + A \tilde{O}(n)$

T_{A} (n) = \tilde{O} (n A)

$T_A(n) = \tilde{O}(n A)$

Tersembunyi Faktor adalah . $\log$ $\log n \log nA$

Chao Xu
sumber

Jika perawatan siapa pun tentang faktor, dengan analisis yang cermat kita dapat membuktikan kompleksitas waktu untuk algoritma Chao adalah . $\log$ $O(nA\log(nA))$

Bukti. Pada lapisan genap dari pohon rekursi, kami mempartisi himpunan menjadi dua himpunan berukuran sama dan , yang menghasilkan $S$ $S_1$ $S_2$

T_{e} (n, A) = T_{o} (n / 2, A^{'}) + T_{o} (n / 2, A - A^{'}) + O (n A \log (n A)),

$T_e(n,A)=T_o(n/2,A')+T_o(n/2,A-A')+O(nA\log(nA)),$ dan pada lapisan ke-3 dari pohon rekursi, kita mempartisi himpunan

menjadi dua "himpunan sama" set

dan

. Lebih tepatnya, kita dapat mempartisi himpunan

dengan jumlah

menjadi dua himpunan

dan

dengan masing-masing jumlah hingga

, dengan paling banyak satu elemen tersisa. Kita dapat menangani elemen itu dengan pemrograman dinamis sepele di

. Ini memberi

S

$S$

S_{1}

$S_1$

S_{2}

$S_2$

S

$S$

A

$A$

S_{1}

$S_1$

S_{2}

$S_2$

\leq A / 2

$\leq A/2$

O (A)

$O(A)$

mana

. Oleh karena itu kami memiliki

T_{o} (n, A) = T_{e} (n_{1}, A / 2) + T_{e} (n - n_{1}, A / 2) + O (n A \log (n A)),

$T_o(n,A)=T_e(n_1,A/2)+T_e(n-n_1,A/2)+O(nA\log(nA)),$

n_{1} = | S_{1} |

$n_1=|S_1|$

mana

, dan

. Ini akan memberi kita

T (n, A) \leq \sum_{i = 1}^{4} T (n_{i}, A_{i}) + O (n A \log (n A)),

$T(n,A)\leq \sum_{i=1}^4T(n_i,A_i)+O(nA\log(nA)),$

\sum_{i = 1}^{4} n_{i} \leq n

$\sum_{i=1}^4n_i\leq n$

\sum_{i = 1}^{4} A_{i} \leq A

$\sum_{i=1}^4A_i\leq A$

\forall i, n_{i} \leq n / 2, A_{i} \leq A / 2

$\forall i,~n_i\leq n/2,~A_i\leq A/2$

T (n, A) = O (n A \log (n A))

$T(n,A)=O(nA\log(nA))$

hqztrue
sumber