Varian lain dari PARTISI

Saya mengalami pengurangan masalah partisi berikut menjadi masalah penjadwalan tertentu:

Input: Daftar bilangan bulat positif dalam urutan yang tidak berkurang. $a_1\leqslant\cdots\leqslant a_n$

Pertanyaan: Apakah ada vektor sedemikian rupa sehingga $(x_1,\ldots,x_n)\in\{-1,1\}^n$

\sum_{saya = 1}^{n} {Sebuah}_{saya} x_{saya} = 0 dan

$\sum_{i=1}^na_ix_i=0\qquad\text{and}$

\sum_{saya = 1}^{k} {Sebuah}_{saya} x_{saya} ⩾ 0 untuk semua k \in {1, ..., n}

$\sum_{i=1}^ka_ix_i\geqslant 0\quad\text{for all }k\in\{1,\ldots,n\}$

Tanpa kondisi kedua itu hanya PARTISI, maka NP-keras. Namun kondisi kedua sepertinya memberikan banyak informasi tambahan. Saya bertanya-tanya apakah ada cara efisien untuk memutuskan varian ini. Atau masih sulit?

cc.complexity-theory reference-request partition-problem subset-sum Thomas Kalinowski
sumber

Jawaban:

Berikut adalah pengurangan dari PARTISI untuk masalah ini. Biarkan $(a_1,\dots, a_n)$ menjadi turunan dari PARTITION. Asumsikan $a_1\leq a_2\leq \dots \leq a_n$ .

Biarkan menjadi “angka yang sangat besar”, mis. . Pertimbangkan instance masalah kita. $N$ $N = (\sum_{i=1}^n |a_i|) + 1$

\underset{5 n waktu}{\underset{⏟}{N, ..., N}}, N + {Sebuah}_{1}, ..., N + {Sebuah}_{n}, \underset{n waktu}{\underset{⏟}{4 N, ..., 4 N}}

$\underbrace{N, \dots, N}_{5n \text{ times}}, N + a_1, \dots, N+a_n,\underbrace{4N, \dots, 4N}_{n \text{ times}}$

Jika ada solusi ke PARTITION kemudian adalah solusi untuk masalah kita. $x_1,\dots, x_n$
$\underset{4 n waktu}{\underset{⏟}{1, ..., 1}}, - x_{1}, ..., - x_{n}, x_{1}, ..., x_{n}, \underset{n waktu}{\underset{⏟}{- 1, ..., - 1}}$ $\underbrace{1, \dots, 1}_{4n \text{ times}},-x_1,\dots,-x_n,x_1,\dots,x_n,\underbrace{-1,\dots,-1}_{n \text{ times}}$
Jika ada solusi untuk turunan masalah kita (yang kita kurangi untuk instance PARTISI menjadi), maka . Jadi Yaitu, adalah solusi untuk PARTITION. $(x_1,\dots,x_{5n},y_1,\dots, y_n, z_1,\dots,z_n)$ $\sum_{i=1}^n a_i y_i \equiv 0 \pmod N$
$\sum_{saya = 1}^{n} {Sebuah}_{saya} y_{saya} = 0.$ $\sum_{i=1}^n a_i y_i = 0.$ $(y_1,\dots, y_n)$

Yury
sumber

Terima kasih Yury. Dalam aplikasi saya, sangat penting bahwa daftar input dipesan secara tidak menurun, dan input dalam reduksi Anda tidak. Saya akan memodifikasi pertanyaan untuk membuat persyaratan pesanan lebih eksplisit.

(N, a_{1}, \dots, a_{n}, N)

$(N,a_1,\ldots,a_n,N)$

Thomas Kalinowski

@ Thomas: Saya tidak menyadarinya. Sekarang saya memperbarui solusi saya.

Yury