Ist dieser spezielle Fall der „Mindestgewichtslösung für lineare Gleichungen“ noch NP-vollständig?

8

Wir in unserer Forschungsgruppe arbeiten an der Anwendung heuristischer Methoden auf das inverse Beleuchtungsproblem (dh angesichts einer Reihe von Einschränkungen hinsichtlich der Beleuchtungsbedingungen in einer Szene finden wir die Orte, an denen die Lichtquellen platziert werden müssen, und ihre Intensitäten in um die Einschränkungen zu erfüllen und die Kosten zu minimieren). Wir möchten die Verwendung heuristischer Methoden rechtfertigen, indem wir beweisen, dass das Problem NP-hart ist, und wir haben festgestellt, dass es in engem Zusammenhang mit dem NP-vollständigen Problem der "Mindestgewichtslösung für lineare Gleichungen" (MWSLE) von Garey und Johnson steht. Computer und Unlösbarkeit ", mit der Besonderheit, dass angesichts der Tatsache, dass Lichtquellenemissionen nicht negativ sein können, die Lösung des linearen Gleichungssystems nur durch nicht negative Werte gebildet werden muss. Zusammenfassend ist das Problem das folgende:


POSITIVE LÖSUNG MIT MINDESTGEWICHT FÜR LINEARE GLEICHUNGEN.

INSTANZ: Endliche Menge von Paaren , wobei ein m-Tupel nicht negativer Ganzzahlen und eine nicht negative Ganzzahl und eine positive Ganzzahl .( Xx bKm(x,b)xbKm

FRAGE: Gibt es ein m-Tupel von nicht negativen rationalen Einträgen, so dass höchstens Einträge ungleich Null hat und dass für alle ?y Kxy =b(x ,b)XyyKxy=b(x,b)X


Garvey und Johnson geben an, dass die NP-Vollständigkeit von MWSLE anhand des Problems der "exakten Abdeckung durch 3 Sätze" nachgewiesen werden kann, geben jedoch keine weiteren Details an. Die genaue Abdeckung durch 3 Sätze ist eine natürliche Verallgemeinerung des Problems der perfekten Anpassung an die Hypergraphen G = (V, E), wobei alle Kanten e∈E 3 Eckpunkte (anstelle von 2) und | V | enthalten ist durch 3 teilbar. Das Problem besteht darin, eine Teilmenge der Hyperkanten so zu finden, dass jeder Scheitelpunkt genau auf eine der ausgewählten Hyperkanten fällt.

Wir versuchen zu beweisen, dass das eingeschränkte Problem immer noch NP-vollständig ist, aber wir sehen keinen Weg, dies zu tun. Irgendwelche Hinweise?

Danke im Voraus

Esteve

schätzen
quelle
1
Bitte fügen Sie Ihrem Beitrag eine Definition der exakten Deckung durch 3 Sätze hinzu, damit die Leute sie nicht selbst in Garey und Johnson (Seite 221) nachschlagen müssen.
Warren Schudy
Erledigt. Ich habe die von Ihnen angegebene Definition in Ihre Antwort aufgenommen.
Wertschätzung

Antworten:

5

Hier ist eine Skizze eines NP-Härtebeweises. Die genaue Abdeckung durch 3 Sätze ist eine natürliche Verallgemeinerung des Problems der perfekten Anpassung an die Hypergraphen wobei alle Kanten 3 Eckpunkte (anstelle von 2) undist teilbar durch 3. Das Problem besteht darin, eine Teilmenge der Hyperkanten so zu finden, dass jeder Scheitelpunkt genau auf eine der ausgewählten Hyperkanten fällt. Sei eine 0/1-Variable für jedes Hyperedge angibt, ob es verwendet wird oder nicht. Klar das Gleichungssysteme E | V | x e eG=(V,E)eE|V|xee

v V.eE:vexe=1 für allevV

hat nur nicht negative Koeffizienten und hat eine Lösung mit höchstens positiven Koeffizienten, wenn eine genaue Abdeckung hat. Die andere Richtung, nämlich zu zeigen, dass dieses System nur dann eine solche Lösung hat , wenn eine genaue Abdeckung hat, ist weniger trivial, aber dennoch einfach.G G.|V|/3G G

Warren Schudy
quelle
Vielen Dank für Ihre schnelle und freundliche Antwort. Ich kämpfe jetzt mit dem weniger trivialen, aber einfachen Teil. Grüße.
Wertschätzung
Es war in der Tat einfach. Wenn das System eine Lösung hat, bilden die Kanten, die den positiven Koeffizienten entsprechen, eine genaue Abdeckung für den Graphen. Jede Gleichung muss mindestens einen positiven Koeffizienten enthalten, damit alle Eckpunkte zur Abdeckung gehören. Auf der anderen Seite hat die Abdeckung nur Eckpunkte, so dass es sich um eine exakte Abdeckung handelt. 3| V||V|33|V|3
Wertschätzung