Was ist der Trick beim Hinzufügen einer großen Zahl bei der Reduzierung von 3-Partition?

7

Problem: Um die des Problems "Packen von Quadraten (mit unterschiedlicher Seitenlänge) in ein Rechteck" zu beweisen , wird reduziert, wie in der folgenden Abbildung gezeigt.NP-Completeness3-Partition

quadratische Verpackung

In der Instanz gibt es Elemente . Die Zielsumme ist .3-Partitionn(a1,,ai,,an)tt=ain/3

Bei der Reduktion ist eine große (konstante) Zahl und jedes wird durch ein Quadrat dargestellt. Die Lücke im Rechteck wird durch Einheitsquadrate ( ) gefüllt .Bai(B+ai)×(B+ai)1×1


Fragen: Ich verstehe den Trick, eine große Zahl in der Reduktion hinzuzufügen, nicht ganz . Ich denke, es wird verwendet, um zu erzwingen, dass jedes Packungsschema eine Lösung für bietet . Aber wie?B3-Partition

Frage 1: Was ist der Trick beim Hinzufügen einer großen Zahl bei der Reduktion von ? Warum funktioniert diese Reduzierung konkret? Warum ist dieser Trick notwendig, dh warum würde die Reduktion nicht funktionieren, wenn wir weglassen würden (setze )?3-PartitionBB=0

Ich habe versucht, den Fehler des Beweises zu identifizieren, dass "jede Verpackung eine 3-Partition ergibt", konnte aber den entscheidenden Punkt nicht ermitteln.

Eigentlich habe ich auch andere Reduzierungen von , die diesen Trick ebenfalls verwenden. Damit,3-Partition

Frage 2: Was ist der allgemeine Zweck dieses Tricks, "eine große Zahl hinzuzufügen" in den Reduzierungen von ( falls vorhanden )?3-Partition


Hinweis: Dieses Problem stammt aus der Videovorlesung (ab 01:15:15) von Prof. Erik Demaine. Ich hätte zuerst das Originalpapier "Quadrate in ein Quadrat packen" prüfen sollen . Es ist mir jedoch im Internet nicht zugänglich. Wenn Sie eine Kopie haben und diese teilen möchten, finden Sie meine Mailbox in meinem Profil. Danke im Voraus.

Hengxin
quelle
Ich habe Demaines Beweis nicht gesehen, aber Sie haben eine Reduktion von einem ähnlichen Problem hier .
RB
Was meinst du mit "Was ist der Trick von ..."? Können Sie Frage 1 genauer formulieren? Meinst du, warum funktioniert diese Reduzierung? Meinst du, warum ist das notwendig, dh warum würde die Reduktion nicht funktionieren, wenn wir weglassen würden (setze )? Etwas anderes? Und wenn Sie es einmal formuliert haben, können Sie uns dann sagen, was Sie versucht haben, diese Frage selbst zu beantworten? BB=0
DW
@ DW Danke für deinen Vorschlag. Ich habe versucht, den Fehler des Beweises zu finden, dass "jede Verpackung eine 3-Partition ergibt", wenn . Ich habe jedoch nicht den Originalbeweis und habe Schwierigkeiten damit. B=0
Hengxin
Meinen Sie damit, dass Sie nicht die Details der Reduzierung von 3-Partition auf Packing Squares haben, sondern nur einen Überblick darüber? Was meinst du mit "dem Originalbeweis"? Was das Papier betrifft, das Sie im Internet nicht finden können: Haben Sie versucht, Ihre lokale Bibliothek zu besuchen, um festzustellen, ob Sie eine Kopie des von Ihnen erwähnten Papiers erhalten, oder haben Sie versucht, die Autoren zu kontaktieren?
DW
@DW Es ist durchaus möglich, dass ich die Antwort aus dem Proof im Papier finde (das nicht zugänglich ist). Dem Umrissbeweis (dem Bild) fehlen zu viele Details. Grundsätzlich möchte ich herausfinden, warum für die Reduktion notwendig ist. Vielleicht kann ich versuchen, die Autoren zu kontaktieren. B
Hengxin

Antworten:

1

Das große dient dazu, sicherzustellen, dass die Quadrate dem in der Abbildung gezeigten Muster folgen.B

Im Teil "Es gibt eine Packung gibt es eine 3-Partition". Sie müssen Trippel von ganzen Zahlen mit sum anzeigen . Dies ist einfach, wenn die Codierungsquadrate in der Verpackung wie im Bild 3-mal-3 angeordnet sind. Aber woher wissen Sie, dass dies der Fall ist? Bei sehr kleinen blauen Quadraten könnten Sie beispielsweise zwei kleine Quadrate nebeneinander in derselben Spalte haben, und dann wären Sie in Schwierigkeiten.=t

Eine Möglichkeit, den Trick der Konstante zu verwenden, besteht darin, zu sagen, dass es nicht möglich ist, dass eine horizontale Linie streng mehr als Quadrate kreuzt (eine solche Linie hat die Länge , ein Quadrat hat die Größe mindestens und ). Jede horizontale Linie trifft also auf ein 1. Quadrat, ein 2. Quadrat usw., und dann können Sie (wieder mit dem großen ) zeigen, dass die ten Quadrate jeder Linie alle in derselben Spalte übereinstimmen müssen. Sobald Sie dies haben, erhalten Sie eine 3-Partition.Bn/3(B+t)n3BB>tn3Bi

In Bezug auf Frage 2 ist es offensichtlich schwierig, eine formale Antwort zu geben, aber das allgemeine Muster ist das folgende: Bei einer 3-Partition müssen Sie eine Art Lockerheit einführen, damit jede Ganzzahl in einem Intervall kann irgendwie codiert und in einen Steckplatz eingebettet (der dann der maximal möglichen Größe entsprechen muss). Ein häufiges Problem ist jedoch, dass zwei Ganzzahlen in denselben Steckplatz passen, oder allgemeiner andere überlappende Probleme (wie bei den Quadraten hier). Dies wird gelöst, indem sichergestellt wird, dass die im Vergleich zur Steckplatzgröße groß genug ist (wir benötigen hier häufig oder ): Dies wird leicht mit einem erreicht additive konstante .[min,max]minmin>max/2min>max(n1)/(n)B

Beispielinstanz bearbeiten, in der erforderlich ist: Die Instanz der 3-Partition sei mit . Dies ist keine Instanz. Mit haben Sie jedoch eine gültige Packung des Rechtecks: Verwenden Sie eine erste Spalte mit vier Quadraten , wobei die letzten beiden nebeneinander liegen, und eine zweite Spalte mit nur . Dies ist beispielsweise mit und einem Rechteck nicht möglich .B(10,7,2,10,9,2)t=20B=040×20(10,7,2,2)(10,9)B=100240×320

Tarulen
quelle