Snížení mezery - Gap reduction

v teorie výpočetní složitosti, a zmenšení mezery je snížení na konkrétní typ rozhodovacího problému, známý jako a c-mezera problém. Tato snížení poskytují informace o tvrdosti přibližný řešení optimalizační problémy. Stručně řečeno, problém mezery se týká problému, kde cílem je rozlišit mezi případy, kdy je nejlepší řešení nad jednou prahovou hodnotou, od případů, kdy je nejlepší řešení pod jinou prahovou hodnotou, takže tyto dvě prahové hodnoty mají mezeru mezi nimi. Redukce mezery lze použít k předvedení výsledků nepřístupnosti, jako by se problém mohl přiblížit lepšímu faktoru než velikosti mezery, pak lze k řešení odpovídajícího problému mezery použít algoritmus aproximace.

c-mezera problém

Definujeme a c-mezera problém jak následuje:^[1] vzhledem k problému P s optimalizací (maximalizací nebo minimalizací) rozlišuje problém ekvivalentní c-mezery mezi dvěma případy pro vstup k a instanci x úlohy P:

{ displaystyle OPT_ {P} (x) leq k}

. Zde má nejlepší řešení instance x úlohy P cenu nebo skóre pod k.

{ displaystyle OPT_ {P} (x)> c cdot k}

. Zde má nejlepší řešení instance x úlohy P cenu nad c⋅k. Mezera mezi těmito dvěma prahy je tedy c.

Všimněte si, že kdykoli OPT spadá mezi prahové hodnoty, neexistuje požadavek na to, jaký by měl být výstup. Platný algoritmus pro problém s mezerou c může odpovědět na cokoli, pokud je OPT uprostřed mezery. Hodnota c nemusí být konstantní; může to záviset na velikosti instance P. Všimněte si, že c-přibližný řešení instance P je přinejmenším stejně těžké jako řešení verze P.

Lze definovat (a, b) -gap problém podobně. Rozdíl je v tom, že prahové hodnoty nezávisí na vstupu; místo toho je dolní prahová hodnota a a horní prahová hodnota b.

Redukce produkující mezeru

Snížení produkující mezeru je a snížení od problému s optimalizací k problému s mezerou c, takže rychlé řešení problému s mezerou c by umožnilo rychlé řešení problému s optimalizací. Termín produkující mezeru vychází z povahy redukce: optimální řešení v optimalizačním problému se mapuje na opačnou stranu mezery od každého jiného řešení redukcí. Vzniká tak mezera mezi optimálním řešením a každým dalším řešením.

Jednoduchým příkladem redukce produkující mezeru je nemetrický Problém obchodního cestujícího (tj. když okrajové náklady grafu nemusí splňovat podmínky a metrický ). Můžeme snížit z Hamiltonova cesta problém na daném grafu G = (V, E) k tomuto problému následovně: zkonstruujeme kompletní graf G '= (V, E') pro problém obchodního cestujícího. Pro každou hranu e ∈ G 'necháme náklady na její procházení 1, pokud e je v původním grafu G a ∞ jinak. Hamiltonovská cesta v původním grafu G existuje právě tehdy, pokud existuje řešení obchodního cestujícího s váhou (| V | -1). Pokud však taková hamiltoniánská cesta neexistuje, pak musí mít cesta nejlepšího obchodního cestujícího váhu alespoň | V |. Hamiltonian Path tedy redukuje na | V | / (| V | -1) -metrový nemetrický obchodní cestující.

Omezení zachování mezery

Snížení zachování mezery je a snížení od problému c-gap k problému c'-gap. Přesněji řečeno, dostaneme instanci x úlohy A s | x | = n a chcete jej snížit na instanci x 'problému B s | x' | = n '. Redukce zachování mezery z A do B je sada funkcí (k (n), k '(n'), c (n), c '(n')), takže

Pro problémy s minimalizací:

OPT_A(x) ≤ k ⇒ OPT_B(x ') ≤ k' a

OPT_A(x) ≥ c⋅k ⇒ OPT_B(x ') ≥ c'⋅k'

Problémy s maximalizací:

OPT_A(x) ≥ k ⇒ OPT_B(x ') ≥ k' a

OPT_A(x) ≤ k / c ⇒ OPT_B(x ') ≤ k' / c '

Pokud c '> c, pak je to a redukce mezery zesilující.

Příklady

Max E3SAT

Tento problém je formou Booleovský problém uspokojivosti (SAT), kde každá klauzule obsahuje tři odlišné literály a chceme maximalizovat počet splněných klauzulí.^[1]

Håstad ukázal, že (1/2 + ε, 1-ε) -gap verze podobného problému, MAX E3-X (N) OR-SAT, je NP-hard.^[2] Problém MAX E3-X (N) OR-SAT je forma SAT, kde každá klauzule je XOR tří odlišných literálů, z nichž přesně jeden je negován. Můžeme snížit z MAX E3-X (N) OR-SAT na MAX E3SAT následujícím způsobem:

Klauzule x_i ⊕ x_j ⊕ x_k = 1 se převede na (x_i ∨ x_j ∨ x_k) ∧ (¬x_i ∨ ¬x_j ∨ x_k) ∧ (¬x_i ∨ x_j ∨ ¬x_k) ∧ (x_i ∨ ¬x_j ∨ ¬x_k)

Klauzule x_i ⊕ x_j ⊕ x_k = 0 se převede na (¬x_i ∨ ¬x_j ∨ ¬x_k) ∧ (¬x_i ∨ x_j ∨ x_k) ∧ (x_i ∨ ¬x_j ∨ x_k) ∧ (x_i ∨ x_j ∨ ¬x_k)

Pokud klauzule není splněna v původní instanci MAX E3-X (N) OR-SAT, mohou být splněny maximálně tři ze čtyř odpovídajících klauzulí v naší instanci MAX E3SAT. Z argumentu mezera vyplývá, že instance problému ANO má splněn alespoň (1-ε) zlomek klauzulí, zatímco instance NO problému má maximálně (1/2 + ε) (1) + (1/2-ε) (3/4) = (7/8 + ε / 4) -frakce klauzulí splněna. Z toho tedy vyplývá, že (7/8 + ε, 1 - ε) -gap MAX E3SAT je NP-tvrdý. Všimněte si, že tato vazba je těsná, protože náhodné přiřazení proměnných dává očekávaný zlomek 7/8 splněných klauzulí.

Obal štítku

The obal štítku problém je definován následovně: daný bipartitní graf G = (A∪B, E), s

A = A₁ ∪ A₂ ∪ ... ∪ A_k, | A | = n a | A_i| = n / k

B = B₁ ∪ B₂ ∪ ... ∪ B_k, | B | = n a | B_i| = n / k

Definujeme „superedge“ mezi A_i a B_j pokud existuje alespoň jedna hrana z A_i do B._j v G, a definujte superedge, který má být pokryt, pokud je alespoň jedna hrana od A_i do B._j je zakryt.

V max. rep verze problému, můžeme si vybrat jeden vrchol z každého A_i a každý B_ia naším cílem je maximalizovat počet krytých super-hran. V min. rep verze, jsme povinni pokrýt všechny supergeby v grafu a chceme minimalizovat počet vrcholů, které vybereme. Manurangsi a Moshkovitz ukázat, že (O (n^1/4), 1) -gapová verze obou problémů je řešitelná v polynomiálním čase.^[3]

Viz také

Reference

^ ^A ^b Demaine, Erik (podzim 2014). „Algoritmické dolní hranice: zábava s tvrdostí Přednáška 12 poznámek“ (PDF).
^ Johan, Hastad (červenec 2001). „Nějaké optimální výsledky nepřístupnosti“. J. ACM. ACM. 48 (4): 798–859. doi:10.1145/502090.502098. S2CID 5120748.
^ Manurangsi, Pasin; Moshkovitz, Dana (2013). "Vylepšené aproximační algoritmy pro projekční hry". Esa 2013. ESA. 8125 (2): 683–694. arXiv:1408.4048. doi:10.1007 / s00453-015-0088-5. S2CID 12959740.

[d-1] A ^b Demaine, Erik (podzim 2014). „Algoritmické dolní hranice: zábava s tvrdostí Přednáška 12 poznámek“ (PDF).

[2] Johan, Hastad (červenec 2001). „Nějaké optimální výsledky nepřístupnosti“. J. ACM. ACM. 48 (4): 798–859. doi:10.1145/502090.502098. S2CID 5120748.

[3] Manurangsi, Pasin; Moshkovitz, Dana (2013). "Vylepšené aproximační algoritmy pro projekční hry". Esa 2013. ESA. 8125 (2): 683–694. arXiv:1408.4048. doi:10.1007 / s00453-015-0088-5. S2CID 12959740.

[1]

[2]

[3]