Apakah NP-sulit untuk mengisi sampah dengan gerakan minimum?

Ada $n$ sampah dan $m$ jenis bola. The $i$ bin th memiliki label $a_{i,j}$ untuk $1\leq j\leq m$ , itu adalah jumlah yang diharapkan dari bola tipe $j$ .

Anda mulai dengan $b_j$ bola dari jenis $j$ . Setiap bola jenis $j$ memiliki berat $w_j$ , dan ingin menempatkan bola ke dalam keranjang yang bin seperti $i$ memiliki berat badan $c_i$ . Distribusi bola sedemikian rupa sehingga kondisi sebelumnya berlaku disebut solusi yang layak.

Pertimbangkan solusi yang layak dengan $x_{i,j}$ bola dari jenis $j$ di bin $i$ , maka biaya yang $\sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}|$. Kami ingin menemukan solusi layak biaya minimum.

Masalah ini jelas NP-keras jika tidak ada batasan pada $\{w_j\}$ . Masalah jumlah subset berkurang ke adanya solusi yang layak.

Namun, jika kita menambahkan kondisi yang $w_j$ membagi $w_{j+1}$ untuk setiap $j$ , maka pengurangan bagian sum karya tidak lagi, sehingga tidak jelas apakah masalah yang dihasilkan tetap NP-keras. Memeriksa adanya solusi yang layak hanya membutuhkan $O(n\,m)$ waktu (terlampir pada akhir pertanyaan), tetapi ini tidak memberikan kita solusi layak biaya minimum.

Masalahnya memiliki formulasi program bilangan bulat yang setara. Mengingat $a_{i,j},c_i,b_j,w_j$ untuk $1\leq i\leq n,1\leq j\leq m$ :

$$\begin{align*} \text{Minimize:} & \sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}| \\ \text{subject to:} & \sum_{j=1}^m x_{i,j}w_j = c_i \text{ for all } 1\leq i\leq n\\ & \sum_{i=1}^n x_{i,j} \leq b_j \text{ for all } 1\leq j \leq m\\ & x_{i,j}\geq 0 \text{ for all } 1 \leq i\leq n, 1\leq j \leq m\\ \end{align*}$$

Pertanyaanku adalah,

Apakah program integer di atas NP-hard ketika $w_j$ membagi $w_{j+1}$ untuk semua $j$ ?

Algoritma untuk memutuskan apakah ada solusi yang layak di $O(n\,m)$ waktu:

Tentukan $w_{m+1}=w_m(\max_{j} c_j + 1)$ dan $d_j = w_{j+1}/w_j$ . Biarkan $a\%b$ menjadi pengingat ketika $a$ dibagi dengan $b$ .

1. Jika ada $c_i$ yang tidak habis dibagi dengan $w_1$ , kembalikan "tidak ada solusi yang layak". (invarian $c_i$ membagi $w_j$ akan selalu dipertahankan dalam loop berikut)

2. untuk $j$ dari $1$ hingga $m$ :

   1. $k \gets \sum_{i=1}^n (c_i/w_j)\%d_j$ . (minimum bola berat$w_j$ wajib)
   2. Jika $b_j<k$ , kembalikan "tidak ada solusi yang layak".
   3. $c_i \gets c_i - ((c_i/w_j)\% d_j)$ untuk semua$i$ . (menghapus jumlah minimum bola diperlukan berat$w_j$ )
   4. $b_{j+1} \gets \lfloor (b_j-k)/d_j \rfloor$ . (kelompokkan bola yang lebih kecil menjadi bola yang lebih besar)
3. kembali "ada solusi yang layak".

Solusi waktu polinomial untuk kasus khusus di mana $n=1$ , dan $w_j$ adalah kekuatan $2$ detik

Diketahui bahwa jika $n=1$ dan semua $w_j$ adalah kekuatan $2$ , maka kasus khusus ini dapat diselesaikan dalam waktu polinomial.

$$\begin{align*} \text{Minimize:} & \sum_{j=1}^m |a_j-x_j| \\ \text{subject to:} & \sum_{j=1}^m w_j x_j = c\\ & 0 \leq x_j \leq b_j \text{ for all } 1\leq j \leq m\\ \end{align*}$$

Solusinya diisyaratkan oleh Yuzhou Gu , dan penulisan dapat ditemukan di sini .

$w_j$$w_{j+1}$$j$

$w_j$$i$$w_j$$w_j$$w_{j+1}$$w_j$$w_{j+1}$$w_j$$j$$w_j$

$w_j$$w_{j+1}$$j$

$n = 1$$w_p$

$w_{j+1}$$w_j * p$$p$$j$$p=2, j=1: p=3, j=2, p=5, j=3, p=7, j=4,...,P, J$$w_j$$w_{j+1}$$j$$w_j$$j$$1, 2, 6, 30, 210, 2310, 30030, ...$$p_j$$j log (j)$, melalui teorema bilangan prima), karena quotients semuanya adalah bilangan prima, kita mendapatkan kompleksitas NP-Intermediate.

$w_{j+1}$$w_j * R_p$$R_p$$j$$w_j$$w_{j+1}$$j$$101, 2657, 7, 3169, 2$$10^{100}$

$w_j$$i$