NP-Härte eines Optimierungsproblems

Während ich ein Problem in der algorithmischen Spieltheorie studierte, interessierte ich mich für die Komplexität der folgenden Optimierungsfrage:

Problem

Gegeben:

Bodenmenge gegeben durch , $U = [n] = \{1,\ldots,n\}$ $n$
$m$ Ranglisten als Gesamtbestellungen wobei ( ), $\langle S_i, \sigma_i \rangle$ $S_i \subseteq U$ $1 \leq i \leq m$
Gewichtsvektor für gegeben durch . $U$ $w \in \mathbb{R}^n$

Ziel: Finden Sie eine Teilmenge die folgende Summe maximiert: wobei ist der am höchsten bewertete Gegenstand in gemäß . $L \subseteq U$

r (L) = \sum_{i \in [m], S_{i} \cap L \neq \emptyset} w (t_{i} (L))

$r(L) = \sum_{i \in [m],\ S_i \cap L \neq \emptyset} w(t_i(L))$

t_{i} (L)

$t_i(L)$

L \cap S_{i}

$L\cap S_i$

σ_{i}

$\sigma_i$

Ich vermute, dass das Problem -hard ist. Tatsächlich scheint das Problem schwierig zu sein, selbst wenn alle die Größe . Dies konnte ich jedoch nicht beweisen. $\mathsf{NP}$ $S_i$ $2$

Was ich weiß

Es ist leicht zu erkennen, dass die folgenden Einschränkungen das Problem leicht machen:

Alle Gewichte sind einheitlich: Die Auswahl aller Elemente ist eindeutig optimal.
Alle Ranglisten sind vollständige Ranglisten über : Die beste Lösung wird erhalten, indem das Element mit dem maximalen Gewicht genommen wird. $U$
Die Gewichte sind nur binär ( ), dann ist die Auswahl aller Wiegeelemente optimal. $w \in \{0,1\}^n$ $1$

Ich konnte jedoch keinen Polynomzeitalgorithmus für den allgemeinen Fall finden (zum Beispiel mit LP). Andererseits sieht es nicht einfach aus, das Problem als -hard zu beweisen . Die Struktur der Probleminstanzen ermöglicht keine einfache Codierung anderer Probleme. (Beachten Sie, dass die Härte des Problems von der Verwendung des gleichen für alle Teilaufträge herrührt. Die Verwendung des gleichen Gewichtsvektors für alle von ihnen macht es jedoch nicht einfach, die Härte zu beweisen.) Ich habe erfolglos versucht, einige -harte Probleme wie Subset-Sum, NAND-Circuit-SAT usw. auf die Entscheidungsversion dieses Problems zu reduzieren (gibt es eine Subset wie ). $\mathsf{NP}$ $L$ $\mathsf{NP}$ $r(L) \geq k$

Eine übereinstimmende IP kann für eine bestimmte Instanz des Problems problemlos leise erstellt werden, aber ich sehe keine ausreichende Ähnlichkeit mit einem mir bekannten Problem.

Frage

Kennen Sie die Komplexität dieses Problems? Gibt es Referenzen, die die Komplexität ähnlicher Optimierungsprobleme untersuchen? Wie würden Sie beweisen, dass dieses Optimierungsproblem -hard ist? (wenn es wirklich schwer ist). $\mathsf{NP}$

cc.complexity-theory ds.algorithms np-hardness optimization JoelO
quelle

Ich denke, Ihre Lösung ist richtig und wenn Sie einen ähnlichen Trick für die Klauseln verwenden, können Sie sogar jedes Si auf 2 Elemente beschränken.

Domotorp

Antworten:

Hier ist eine mögliche Lösung:

Die Ermäßigung erfolgt ab 3SAT.

Eingabe: DNF-Klauseln über Variablen . $m$ $(\varphi_1,\ldots,\varphi_m)$ $n$ $(x_1,\ldots,x_n)$

Reduktion: Erstellen Sie für jede Variable eine Reihe von Elementen, die aus zwei Elementen bestehen: , entsprechend einer Zuordnung entweder zur Variablen oder ihrer Negation, plus einem Hilfselement . Der Preis aller Artikel sei und der Preis von sei . $x_i, \overline x_i$ $True$ $x_i$ $t$ $\{x_i,\overline x_i\}_{i=1,…,n}$ $1$ $t$ $1.5$

Erstellen Sie zwei Gruppen von Verbrauchern:

Satz 1: Gültigkeitsrangfolge: Diese Gruppe von Verbrauchern codiert die Gültigkeitsbeschränkungen für die Zuweisungen zu . Das heißt, dass genau einer von jedem auf (dh vom Algorithmus übernommen wird). Für jedes vier Teilrankings erstellt: $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$

Die Einnahme von kann niemals schaden, daher gehen wir davon aus, dass es immer gewählt wird. Wenn sowohl als auch ausgewählt sind, erhalten wir eine Auszahlung . Wenn keiner von ihnen ausgewählt ist, erhalten wir eine Auszahlung von . Wenn einer von ihnen ausgewählt wird, erhalten wir eine Auszahlung von . $t$ $x_i$ $\overline x_i$ $4$ $3$ $4.5$

Set 2: Klausel-Rangliste. Für jede Klausel der Form erstellen wir eine Rangfolge: . Wenn erfüllt ist, bedeutet dies , dass zumindest eines der Elemente zu entsprechenden und ausgewählt ist, die eine zusätzliche Auszahlung gibt aus Ranking . $\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$

Jetzt ist die 3CNF-Formel genau dann erfüllbar, wenn es eine Reihe von Elementen gibt, die eine Auszahlung von . $m+4.5n$

JoelO
quelle