Kekerasan NP dari kasus khusus Pemisahan Nomor

12

Pertimbangkan masalah berikut,

  • Mengingat satu set bilangan positif { a 1 , ... , a n } dimana k ≥ 3 adalah konstanta, kita ingin partisi set ke m himpunan bagian dari ukuran k sehingga produk dari jumlah setiap bagian dimaksimalkan.n=km{a1,…,an}k≥3mk

Masalahnya sangat mirip dengan partisi nomor -way yang terkenal kecuali kita memiliki batasan pada jumlah angka di setiap partisi. Untuk k = 2 algoritma polinomial sederhana berikut dapat diusulkan,mk=2

  • anggap angkanya diurutkan, yaitu . Kemudian, untuk i ≤ m assign sebuah i untuk subset i , untuk i > m , menetapkan ke subset n - i + 1 .a1<a2<...<ani≤maiii>mn−i+1

Tidak sulit untuk melihat mengapa algoritma ini bekerja. Pilih saja dua nampan sembarang. Setiap swap dalam angka tidak akan menambah jumlah produk.

Tetapi untuk lebih besar , saya bertanya-tanya apakah masalahnya dapat diselesaikan dalam waktu polinomial atau tidak? Saya juga akan berterima kasih jika seseorang dapat menunjukkan itu np-kekerasan.k

Catatan: Saya mengalami masalah saat saya sedang mengerjakan masalah penjadwalan di jaringan nirkabel. Saya menemukan algoritma heuristik yang bagus untuk menyelesaikan masalah. Tetapi setelah beberapa saat saya pikir masalahnya mungkin secara teori menarik.

cc.complexity-theory np-hardness application-of-theory polynomial-time Helium
sumber
2
k=2
2
@Mohsen, terima kasih. Saya menyarankan agar Anda memasukkan komentar ini tentang motivasi, latar belakang, dan apa yang Anda ketahui tentang kasus k = 2 dalam pertanyaan. Itu mungkin akan membuatnya lebih menarik bagi orang lain.
Kaveh
4
Intuisi saya adalah bahwa produk dari jumlah setiap subset dimaksimalkan ketika jumlahnya sama atau perbedaan berpasangan maksimum minimum. Di bawah asumsi ini, kita mendapatkan pengurangan mudah dari 3-partisi yang NP-complete (untuk k = 3).
Mohammad Al-Turkistany
3
(Saya menghapus dua komentar yang saya posting beberapa jam yang lalu untuk menulis ulang lebih akurat.) Seperti yang disarankan turkistany, masalah k-partisi dapat direduksi menjadi masalah ini, dan oleh karena itu masalah ini NP-hard untuk setiap k≥3 konstan. Satu-satunya properti yang relevan adalah bahwa maksimum produk dari jumlah paling tidak adalah ((a_i / k) ^ m jika dan hanya jika angka-angka dapat dipartisi menjadi m set masing-masing dengan ukuran k yang jumlahnya semua sama. Produk tidak selalu dimaksimalkan oleh partisi yang meminimalkan perbedaan berpasangan maksimum, tetapi itu tidak relevan selama kami mempertimbangkan masalah yang sebenarnya. (selengkapnya)
Tsuyoshi Ito
3
(lanjutan) Jika Anda memerlukan input untuk menjadi set daripada multiset , reduksi ini masih berfungsi karena masalah k-partisi tetap NP-complete bahkan dengan set, tetapi hati-hati karena bukti standar kelengkapan NP dari masalah 3-partisi hanya berfungsi ketika input diizinkan mengandung bilangan bulat yang sama lebih dari sekali. Lihat Kompleksitas komputasi masalah 3-partisi dengan angka berbeda (perhatian: promosi-sendiri).
Tsuyoshi Ito

Jawaban:

11

(Ini adalah versi sedikit lebih rinci dari komentar saya pada pertanyaan.)

Seperti yang disarankan turkistany dalam komentar pada pertanyaan, masalah ini adalah NP-hard untuk setiap konstanta k ≥3 dengan pengurangan dari masalah partisi- k . Pengurangan tidak mengubah contoh sama sekali: hanya perhatikan bahwa maksimum produk dari jumlah paling tidak adalah ( a i / k ) m jika dan hanya jika angka dapat dipartisi menjadi m set masing-masing dengan ukuran k yang jumlahnya semua sama.

Perhatikan bahwa input untuk masalah partisi- k biasanya didefinisikan sebagai angka km yang mungkin tidak semuanya berbeda , dan ini sangat penting dalam bukti standar kelengkapan NP-nya (seperti yang ada di Garey dan Johnson ). Oleh karena itu, pengurangan di atas hanya membuktikan NP-hardness dari sedikit generalisasi dari masalah saat ini di mana input diperbolehkan menjadi multiset, bukan set. Namun, celah ini dapat diisi karena masalah k- partisi tetap NP-lengkap bahkan jika angka-angka dalam input harus semua berbeda; lihat [HWW08] untuk kasus k = 3 (lihat juga jawaban Serge Gaspersuntuk pertanyaan lain), yang dapat dimodifikasi dengan mudah untuk nilai k yang lebih besar .

Selain itu, semua yang dinyatakan di sini tetap NP-complete / NP-hard bahkan ketika angka-angka dalam input diberikan secara unary.

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger. Realisasi multigraf dari urutan derajat: Maksimal mudah, minimisasi sulit. Operations Research Letters , 36 (5): 594–596, September 2008. http://dx.doi.org/10.1016/j.orl.2008.05.004

Tsuyoshi Ito
sumber