NP-Hardness dari kasus khusus masalah pengemasan ortogonal

9

Biarkan menjadi seperangkat bentuk persegi panjang dimensional. Untuk dan , menjelaskan panjang dalam dimensi . Notasi yang sama digunakan untuk wadah . Masalah pengemasan orthogonal dimensional (OPP- ) adalah memutuskan apakah cocok dengan wadah tanpa tumpang tindih. Secara formal, masalahnya adalah untuk mengetahui apakah ada fungsi , sehinggaVDd{1,...,D}vVwd(v)Q+vdCDDVCd{1,...,D}fd:VQ+vV,fd(v)+wd(v)wd(C) dan , , .v1,v2V(v1v2)[fd(v1),fd(v1)+wd(v1))[fd(v2),fd(v2)+wd(v2))=

Masalahnya adalah NP-lengkap (lihat Fekete SP, Schepers J. "Pada pengemasan dimensi tinggi I: Modeling". Laporan Teknis 97-288, Universitas di zu Köln, 1997). Masalahnya adalah NP-lengkap bahkan untuk . Saya bertanya-tanya, apakah masalah pengemasan ortogonal untuk jumlah jenis yang terbatas (yaitu ukuran di setiap dimensi) item masih lengkap atau tidak NP. Sampai sekarang saya menemukan hasil di beberapa makalah tentang NP-kelengkapan kotak pengemasan menjadi persegi (lihat JOSEPH YT. LEUNG, TOMMY W. TAM, DAN CS WONG, "Pengemasan kotak menjadi kotak", Journal of Parallel and Distributed Computing, Volume 10 Edisi 3, November 1990) yang sudah menjadi batasan tetapi saya masih tidak tahu apa yang terjadi ketika jumlah jenis barang dibatasi.D=2

Terima kasih atas jawaban Anda,

Petru
sumber
3
dapatkah Anda menyebutkan masalah aslinya?
Suresh Venkat
Apa masalah kemasan ortogonal?
Tsuyoshi Ito
2
(1) Saya bukan ahli dalam hal ini, tetapi bukankah discription masalah terlalu samar untuk menganalisis kompleksitasnya? (2) Silakan coba menggunakan komentar orang lain untuk meningkatkan pertanyaan Anda dengan mengeditnya, daripada menambahkan lebih banyak komentar. Kebanyakan orang tidak ingin mengikuti diskusi dalam komentar hanya untuk memahami pertanyaannya.
Tsuyoshi Ito
2
Mungkin mencoba mendefinisikan dengan seksama apa masalahnya dengan mengedit pertanyaan Anda (klik tombol edit di atas), dan tambahkan beberapa referensi yang Anda temukan. Itu akan membantu masyarakat memahami apa yang Anda ketahui, dan apa yang ingin Anda ketahui. Bantu kami untuk membantu Anda!
Hsien-Chih Chang 張顯 之
(Komentar saya dan komentar Hsien-Chih merujuk pada komentar si penanya sebelumnya yang menggambarkan masalah pengemasan ortogonal, yang telah dihapus kemudian.)
Tsuyoshi Ito

Jawaban:

7

Saya pikir makalah yang ditulis oleh Klaus Jansen dan Roberto Solis-Oba " Algoritma OPT + 1 untuk Masalah Stok dengan Jumlah Konstan Panjang Objek " memiliki jawaban parsial untuk pertanyaan Anda. Mereka menganggap kasus khusus masalah Anda yang dikenal sebagai masalah Pemotongan Stok ketika jumlah jenis objek yang berbeda konstan dan didefinisikan sebagai berikut:

Dalam masalah pemotongan stok kita diberikan satu set dari tipe objek, di mana objek tipe memiliki panjang integer positif . Mengingat di fi nite set tempat sampah, masing-masing berkapasitas bilangan bulat , masalahnya adalah untuk membawa set dari objek ke minimum kemungkinan jumlah sampah sedemikian rupa bahwa kapasitas sampah tidak terlampaui; di set ada objek tipe , untuk semua .T={T1,T2,,Td}TipiβOnOniTii=1,,d

Penulis mengklaim itu

tidak diketahui apakah masalah stok pemotongan dapat diselesaikan dalam waktu polinomial untuk setiap nilai tetap .d

Dan mereka mengusulkan pendekatan polinomial-waktu algoritma ketika diperbaiki.OPT+1d

Karena tidak terbukti bahwa kasus khusus ini dalam , ini adalah bukti bahwa masalah Anda adalah .PNP

Addendum: itu dikenal bahwa kasus dengan dua jenis objek ( ) adalah polynomially dipecahkan, tetapi untuk ada hanya diketahui -approximation.d=2d=3OPT+1

Oleksandr Bondarenko
sumber
Terima kasih atas jawaban Anda. Itu tidak terbukti berada di , tetapi bukan NP-keras kan? Bagaimanapun, seperti yang Anda katakan itu memberi saya jawaban parsial dan membuat saya berpikir bahwa untuk OPP-2 itu kemungkinan besar tidak dipelajari. P
Petru
Saya pikir Anda mungkin benar bahwa masalah Anda tidak dipelajari. Seperti yang Anda katakan "Itu tidak terbukti berada di P, tetapi tidak NP-keras" dan saya memahaminya dengan cara ini juga.
Oleksandr Bondarenko
2
Mungkin masalah ini dapat ditambahkan ke daftar masalah "tidak diketahui berada di P atau sedang NPC".
Hsien-Chih Chang 張顯 之