NP-hardness dari masalah optimisasi

Saat mempelajari masalah dalam teori permainan algoritmik, saya tertarik pada kompleksitas pertanyaan pengoptimalan berikut:

Masalah

Diberikan:

• set tanah diberikan oleh n ,$U = [n] = \{1,\ldots,n\}$$n$
• peringkat diberikan sebagai total pesanan ⟨ S i , σ i ⟩ mana S i ⊆ U ( 1 ≤ i ≤ m ),$m$$\langle S_i, \sigma_i \rangle$$S_i \subseteq U$$1 \leq i \leq m$
• vektor berat untuk diberikan oleh w ∈ R n .$U$$w \in \mathbb{R}^n$

Tujuan: menemukan subset memaksimalkan jumlah berikut: r ( L ) = Σ i ∈ [ m ] , S i ∩ L ≠ ∅ w ( t i ( L ) ) di mana t i ( L ) adalah peringkat item yang tertinggi di L ∩ S i menurut σ i .$L \subseteq U$

Saya menduga bahwa masalahnya adalah -hard. Sebenarnya masalah tampaknya sulit bahkan ketika semua S i adalah dari ukuran 2 . Namun saya belum bisa membuktikan ini.$\mathsf{NP}$$S_i$$2$

Apa yang saya tahu

Mudah untuk melihat bahwa pembatasan berikut membuat masalah mudah:

• semua bobotnya seragam: memilih semua elemen jelas optimal.
• semua peringkat adalah peringkat lengkap di atas : solusi terbaik diperoleh dengan mengambil elemen dengan berat maksimal.$U$
• bobotnya hanya biner ( ), lalu memilih semua elemen penimbangan 1 adalah optimal.$w \in \{0,1\}^n$$1$

$\mathsf{NP}$$L$$\mathsf{NP}$$r(L) \geq k$

IP yang cocok dapat dibangun dengan mudah untuk contoh masalah tertentu, tetapi saya tidak melihat adanya kemiripan yang cukup dengan masalah yang saya ketahui.

Pertanyaan

$\mathsf{NP}$

Nah, inilah solusi yang mungkin:

Pengurangan akan dari 3SAT.

$m$$(\varphi_1,\ldots,\varphi_m)$$n$$(x_1,\ldots,x_n)$

$x_i, \overline x_i$$True$$x_i$$t$$\{x_i,\overline x_i\}_{i=1,…,n}$$1$$t$$1.5$

Buat dua set konsumen:

$x_1,\ldots,x_n$$\{x_i,\overline x_i\}$$True$$i=1,\ldots,n$

$\sigma_{i1}: x_i\succ t\\ \sigma_{i2}: \overline x_i \succ t \\ \sigma_{i3}: x_i \succ \overline x_i \\ \sigma_{i4}: x_i \succ \overline x_i$

$t$$x_i$$\overline x_i$$4$$3$$4.5$

$\varphi_j=\ell_{j1} \vee \ell_{i2} \vee \ell_{j3}$$\sigma_j: \ell_{j1} > \ell_{j2} > \ell_{j3}$$\varphi_j$$\ell_{j1}, \ell_{j2}$$\ell_{j3}$$1$$\sigma_j$

$m+4.5n$