Teilmengenproblem mit vielen Teilbarkeitsbedingungen

28

Sei eine Menge natürlicher Zahlen. Wir betrachten unter der Teilbarkeits-Teilordnung, dh . LassenSSs1s2s1s2

α(S)=max{|V|VS,V an antichain } .

Was können wir über die Komplexität des Problems in Bezug auf \ alpha (S) sagen, wenn wir das Teilmengen-Summenproblem betrachten, bei dem sich die Mehrfachmenge von Zahlen in S befindet ? Es ist einfach zu sehen, ob \ alpha (S) = 1 ist , dann ist das Problem einfach. Beachten Sie, dass es auch für das schwierigere Rucksackproblem einfach ist, wenn \ alpha (S) = 1 \ Dolch ist .α(S)α(S)=1α(S)=1


Sequentielle Rucksackprobleme lösen von M. Hartmann und T. Olmstead (1993)

Chao Xu
quelle
1
Anstelle von "Beziehung" schlage ich vor, die Begriffe "Teilordnung" zu verwenden. Auf den ersten Blick könnte das Problem mit den Frobenius-Münzen relevant sein (natürlich nicht sicher)
Aryabhata,

Antworten:

2

Dieses Problem kann in Polynomialzeit durch lineare Programmierung gelöst werden, und dies gilt tatsächlich für jede Teilordnung (S,) . Übrigens können wir durch Induktion beweisen, dass es für jede endliche Teilordnungsmenge (S,) eine endliche Menge SN und eine Bijektion f:SS , so dass für alle s1,s2S,s1s2f(s1)|f(s2) .

Sei C die Menge, die durch die Ketten in S . Denken Sie daran, dass C eine Kette iff für alle v,v in C , vv oder vv

Erstellen für jedes eine boolesche Variable für jede Kette eine boolesche Variable . Wir können das folgende lineare Programm für unser Problem schreiben : xvvSyCC(P)

MaxvSxvsubject tovCxv1,CCxv{0,1},vS

und sein Dual :(D)

MinCCyCsubject toC:vCyC1,vSyC{0,1},CC

Dann ist das Problem, die minimale Deckung eines bestellten Satzes durch Ketten zu finden, das Doppelte unseres Problems. Der Satz von Dilworth besagt das

Es gibt eine Antikette A und eine Aufteilung der Ordnung in eine Familie P von Ketten, so dass die Anzahl der Ketten in der Aufteilung der Kardinalität von A entspricht

was bedeutet, dass die optimale Lösung dieser beiden Probleme übereinstimmt:Opt(P)=Opt(D)

Sei ( bzw. ) die Relaxation von ( bzw. ), dh dasselbe lineare Programm, in dem alle Bedingungen ( bzw. ) werden durch ( bzw. ) ersetzt. Sei und ihre optimale Lösung. Seit wir: und schwache Dualität Theorem legt fest, dass(P) (D)(P) (D)xv{0,1} yC{0,1}xv[0,1] yC[0,1]Opt(P)Opt(D){0,1}[0,1]

Opt(P)Opt(P) and Opt(D)Opt(D)
Opt(P)Opt(D)dann, indem wir alles zusammensetzen, haben wir:
Opt(P)=Opt(P)=Opt(D)=Opt(D)

Dann können wir mit der Ellipsoidmethode ( ) in Polynomzeit berechnen. Es gibt eine exponentielle Anzahl von Einschränkungen, aber es gibt ein Polynom-Zeittrennungs-Orakel. In der Tat können wir bei gegebener Lösung alle Paare aufzählen und prüfen, ob oder , und daher in polynomieller Zeit entscheiden, ob durchführbar ist oder auf andere Weise die mit der Kette verbundene Beschränkung ist verletzt.Opt(P)=Opt(P)Xs1,s2Xs1s2s2s1X{v1,v2}

Mathieu Mari
quelle
Die Ellipsenmethode funktioniert unabhängig von der Anzahl der Nebenbedingungen, wenn wir (1) eine polynomielle Anzahl von Variablen und (2) ein Trennungsorakel haben, das bei jeder Lösung in polynomieller Zeit entscheidet, ob durchführbar ist oder eine von verletzte Nebenbedingung findet . Ich empfehle [ www-math.mit.edu/~goemans/18433S09/ellipsoid.pdf] zu lesen , Wikipedia ist in diesem Punkt nicht sehr klarxxx
Mathieu Mari
Vielen Dank für die Erklärung, warum die exponentielle Anzahl von Nebenbedingungen kein Problem darstellt, und für die Relevanz der Dualität. Sehr schön!
DW