NP-Vollständigkeit für ganzzahlige lineare Programm

Question

Dies ist ein Hausaufgabenproblem, also will ich die Lösung nicht.Ich brauche einen Hinweis, welches Problem auf das Folgende reduziert wird und / oder wie man anfängt.Wir dachten an TSP oder ein unabhängiges Set, konnte aber nicht mit einer Lösung kommen.

wir haben $ i \ ldots j $ speichern und $ i \ ldots n $ mögliche Orte zuBauen Sie ein neues Lager auf.Kosten zum Erstellen eines neuen Lagerlagers sind $ c_j $ .Zwischen jedem Laden und dem Warehouse ist ein Pfad der Kosten $ d_ {i, j} $ .Jeder Laden muss mit mindestens einem Lager verbunden sein.

Das Entscheidungsproblem ist: Gibt es eine Reihe von Lagern und Pfaden, damit die Summe kleiner als eine bestimmte Anzahl $ k $ ist.

Answer 1

Dies ist ein Klassiker Standortprobleme . Dieser Wikipedia-Artikel schlägt nahe, dass NP-Härte durch Reduktion von abdeckung nachweisen kann. .

---

Da der Asker nun gesagt hat, dass er eine Lösung gefunden hat, indem er von vertex abdeckung gesenkt wurde, werde ich fortfahren und die Reduktion von set cover :

für jeden Wert ein Geschäft erstellen; Erstellen Sie für jedes Set ein Lagerhaus. Weisen Sie die Kosten jedes Lagerlagers ab, um zu sein. Dann baut die minimale Kostenlösung für das Anlagenproblem genau den Satz von Lagerhäusern, die der minimalen Set-Abdeckung im ursprünglichen Problem entsprechen.
Kummer Der Wert $ K $ wird verwendet, um das Optimierungsproblem (Minimieren Sie die Sätze / Kosten) in ein Entscheidungsproblem (Gibt es eine Lösung mit nicht mehr als $ K $ Sets / Kosten?). Der $ k $ aus der Set-Cover-Instanz ist derselbe wie der $ K $ im Problem der Anlage Wenn Sie die "willkürlich kleinen" Werte für genau 0 einstellen dürfen, müssen Sie möglicherweise den Wert mit einem beliebigen Betrag füllen, jedoch weniger als 1, solange Sie die "willkürlich kleinen" Gewichte auswählen, um klein genug zu sein. Sie brauchen nur die Summe aller "willkürlich kleinen" Kosten für weniger als 1, und jeder "willkürlich große" Kosten ist größer als die Summe der Kosten aller Lagern und allen "willkürlich kleinen" Routen.
Kummer Beachten Sie, dass Sie, wenn nur ganzzahlige Kosten in den Einrichtungsproblemen zulässig sind, immer noch das gleiche Ergebnis erzielen, indem Sie alle Kosten durch den am wenigsten gemeinsamen Multiple skalieren.