L-Reduktion

Im Informatikinsbesondere das Studium von Näherungsalgorithmen, einL-Reduktion (""lineare Reduktion") ist eine Transformation von Optimierungsprobleme welche linear die Merkmale von Annachkenntnissen bewahrt; es ist eine Art von Annäherungsrückverringerung. L-Reduktionen in Studien über ungefähre Optimierungsprobleme spielen eine ähnliche Rolle wie die von Polynomverringerungen in den Studien von Rechenkomplexität von Entscheidungsprobleme.

Der Begriff L Reduktion wird manchmal verwendet, um sich darauf zu beziehen Log-Raum-ReduzierungenAnalogie zur Komplexitätsklasse L, aber das ist ein anderes Konzept.

Definition

Lass a und b sein Optimierungsprobleme und C_A und C_B ihre jeweiligen Kostenfunktionen. Ein Paar Funktionen f und g ist eine L-Reduktion, wenn alle folgenden Bedingungen erfüllt sind:

Funktionen f und g sind berechnet in Polynomzeit,
wenn x ist dann eine Instanz von Problem A, dann f(x) ist eine Instanz von Problem B,
wenn y ' ist eine Lösung für f(x), dann g(y ' ) ist eine Lösung für x,
Es gibt eine positive konstante α so, dass

oder

,

Es gibt ein positives konstantes β, so dass für jede Lösung y ' zu f(x)

oder B} (y ') |}

.

Eigenschaften

Implikation der PTA -Reduktion

Eine L-Reduktion von Problem A zu Problem B impliziert a AP-Reduktion Wenn a und b Minimierungsprobleme sind und a PTA -Reduktion Wenn A und B Maximierungsprobleme sind. In beiden Fällen, wenn B ein PTA hat und es eine L-Reduktion von A nach B gibt, hat A auch ein PTAs.^[1]^[2] Dies ermöglicht die Verwendung der L-Reduktion als Ersatz, um die Existenz einer PTAS-Reduktion zu zeigen. Crescenzi hat vorgeschlagen, dass die natürlichere Formulierung der L-Reduktion in vielen Fällen aufgrund der einfachen Nutzung tatsächlich nützlicher ist.^[3]

Beweis (Minimierungsfall)

Lassen Sie das Approxationsverhältnis von B sein ${\ displayStyle 1+ \ Delta}$ . Beginnen Sie mit dem Annäherungsverhältnis von a, ${\ displayStyle {\ frac {c_ {a} (y)} {\ mathrm {opt} _ {a} (x)}}}$ . Wir können absolute Werte um den dritten Zustand der L-Reduktionsdefinition entfernen, da wir wissen, dass A und B Minimierungsprobleme sind. Ersetzen Sie diese Bedingung, um zu erhalten

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq {\frac {\mathrm {OPT} _{A}(x)+\ Beta (c_ {b} (y ')-\ mathhrm {opt} _ {b} (x')} {\ mathhrm {opt} _ {a} (x)}}

Vereinfachung und Ersetzen der ersten Bedingung haben wir

{\ displayStyle {\ frac {c_ {a} (y)} {\ mathrm {opt} _ {a} (x)} \ leq 1+ \ alpha \ beta \ links ({\ frac {c_ {b} ( y ')-\ mathhrm {opt} _ {b} (x')} {\ mathhrm {opt} _ {b} (x ')}} \ rechts)}

Aber der Begriff in Klammern auf der rechten Seite ist tatsächlich gleich ${\ displayStyle \ Delta}$ . Somit ist das Annäherungsverhältnis von a ${\ displayStyle 1+ \ alpha \ Beta \ Delta}$ .

Dies entspricht den Bedingungen für die AP-Reduktion.

Beweis (Maximierungsfall)

Lassen Sie das Approxationsverhältnis von B sein ${\ displaystyle {\ frac {1} {1- \ delta '}}}$ . Beginnen Sie mit dem Annäherungsverhältnis von a, ${\ displayStyle {\ frac {c_ {a} (y)} {\ mathrm {opt} _ {a} (x)}}}$ . Wir können absolute Werte um den dritten Zustand der L-Reduktionsdefinition entfernen, da wir wissen, dass A und B Maximierungsprobleme sind. Ersetzen Sie diese Bedingung, um zu erhalten

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq {\frac {\mathrm {OPT} _{A}(x)-\ Beta (c_ {b} (y ')-\ mathhrm {opt} _ {b} (x')} {\ mathhrm {opt} _ {a} (x)}}

Vereinfachung und Ersetzen der ersten Bedingung haben wir

{\ displayStyle {\ frac {c_ {a} (y)} {\ mathrm {opt} _ {a} (x)} \ geq 1- \ alpha \ beta \ links ({\ frac {c_ {b} ( y ')-\ mathhrm {opt} _ {b} (x')} {\ mathhrm {opt} _ {b} (x ')}} \ rechts)}

Aber der Begriff in Klammern auf der rechten Seite ist tatsächlich gleich ${\ displayStyle \ Delta '}$ . Somit ist das Annäherungsverhältnis von a ${\ displaystyle {\ frac {1} {1- \ alpha \ Beta \ Delta '}}}}$ .

Wenn ${\ displaystyle {\ frac {1} {1- \ alpha \ Beta \ Delta '}} = 1+ \ Epsilon}}$ , dann $oder$ , der den Anforderungen an die PTA-Reduzierung entspricht, aber nicht der AP-Reduktion.

Andere Eigenschaften

L-Reduktionen implizieren auch P-Reduktion.^[3] Man kann ableiten, dass L-Reduktionen PTA-Reduzierungen aus dieser Tatsache und die Tatsache implizieren, dass P-Reduktionen PTA-Reduzierungen implizieren.

L-Reduktionen bewahren die Mitgliedschaft in APX nur für den Minimierungsfall auf, um AP-Reduktionen zu implizieren.

Beispiele

Dominierender Satz: Ein Beispiel mit α = β = 1
Token -Rekonfiguration: Ein Beispiel mit α = 1/5, β = 2

Siehe auch

Verweise

^ Kann, Viggo (1992). Über die Annäherung an NP-Complete \ mathRM {opt} iMization-Probleme. Royal Institute of Technology, Schweden. ISBN 978-91-7170-082-7.
^ Christos H. Papadimitriou; Mihalis Yannakakis (1988). "\ mathrm {opt} iMization, Approximation und Komplexitätsklassen". STOC '88: Verfahren des zwanzigsten jährlichen ACM -Symposiums über die Theorie des Computers. doi:10.1145/62212.62233.
^ ^a ^b Crescenzi, Pierluigi (1997). "Ein kurzer Leitfaden zur Erhaltung von Annäherungserhaltungen". Verfahren der 12. jährlichen IEEE -Konferenz zur Berechnung der Komplexität. Washington, D.C.: IEEE Computer Society: 262–.

G. Ausiello, P. Crescenzi, G. Gamsisi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Komplexität und Näherung. Kombinatorische Optimierungsprobleme und deren Annachkenntnisse. 1999, Springer. ISBN3-540-65431-3

[Kann92-1] Kann, Viggo (1992). Über die Annäherung an NP-Complete \ mathRM {opt} iMization-Probleme. Royal Institute of Technology, Schweden. ISBN 978-91-7170-082-7.

[Papadimitriou88-2] Christos H. Papadimitriou; Mihalis Yannakakis (1988). "\ mathrm {opt} iMization, Approximation und Komplexitätsklassen". STOC '88: Verfahren des zwanzigsten jährlichen ACM -Symposiums über die Theorie des Computers. doi:10.1145/62212.62233.

[crescenzi-3] Crescenzi, Pierluigi (1997). "Ein kurzer Leitfaden zur Erhaltung von Annäherungserhaltungen". Verfahren der 12. jährlichen IEEE -Konferenz zur Berechnung der Komplexität. Washington, D.C.: IEEE Computer Society: 262–.

[1]

[2]

[3]