FT
A
R. Královič
R
Aproximačné algoritmy
D
(7. októbra 2010)
R
D
FT
A
ii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
1
4
6
2 Optimalizačné problémy
2.1 Triedy Po a NPo . . . . . . . . . . . . . . .
2.2 Redukovateľnosť . . . . . . . . . . . . . . .
2.3 Vzťah medzi NP a NPo . . . . . . . . . . . .
2.4 Aproximácia . . . . . . . . . . . . . . . . . .
2.4.1 Absolútna aproximácia . . . . . . . .
2.4.2 Relatívna aproximácia – trieda APX
2.4.3 Lepšie ako APX: PTAS a FPTAS . .
2.4.4 Horšie ako APX . . . . . . . . . . .
2.4.5 Asymptotická aproximácia . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
9
10
11
12
13
13
15
17
20
3 Techniky návrhu aproximačných algoritmov
3.1 Greedy algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Lineárne programovanie . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Edmondsov algoritmus . . . . . . . . . . . . . . . . . . .
3.3 Derandomizácia . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Metóda podmienených pravdepodobností . . . . . . . .
3.3.2 Derandomizácia aplikovaná na problém MAX-E3-SAT
3.4 Vonkajškoplanárna dekompozícia . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23
23
25
28
32
32
32
34
4 Negatívne výsledky o aproximácii
4.1 Pravdepodobnostne overiteľné dôkazy (PCP) . . . . . . . . . . . . .
4.2 Použitie PCPvety . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
39
40
5 Redukcia a úplnosť v triedach aproximovateľnosti
5.1 NPo -úplnosť . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 APX-úplnosť . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
46
50
6 Problém obchodného cestujúceho
6.1 Trojuholníková nerovnosť – Christofidesov algoritmus . . . . . . . .
6.2 Metrický TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Stabilita aproximácie . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
55
57
66
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
D
R
A
1 Úvod
1.1 Algoritmy a zložitosť . .
1.2 Lineárne programovanie
1.3 Použité vzťahy . . . . .
1.4 Teória pravdepodobnosti
FT
Obsah
iii
iv
OBSAH
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
69
70
72
75
78
kostry
Metric Steiner tree . . . . . . . . . . . . .
Steiner tree . . . . . . . . . . . . . . . . .
Steiner forest . . . . . . . . . . . . . . . .
Steiner network . . . . . . . . . . . . . . .
Constrained MST via matroid intersection
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
81
81
81
81
81
81
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
D
R
A
8 Stromy a
8.0.1
8.0.2
8.0.3
8.0.4
8.0.5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
FT
7 Toky a rezy
7.1 Multiway-Cut
7.2 Min-k-Cut . . .
7.3 Min-Multicut .
7.4 Max-Cut . . . .
Kapitola 1
FT
Úvod
Tento text obsahuje poznámky k predmetu ”Aproximačné algoritmy” prednášanému na FMFI UK. Momentálne je v stave pre-α a obsahuje útržky poznámok,
kusy textu a veľa chýb v pomerne nesúrodej zmesi. Čiteteľný je zatiaľ iba na vlastné
riziko.
V tejto kapitole zhrnieme základné vedomosti, na ktorých kurz stavia.
Algoritmy a zložitosť
A
1.1
• algoritmy, RAM, počet operácií, unit cost vs. log cost
• praktická riešiteľnosť - polynomiálny čas
• Turingove stroje, polynomiálna ekvivalencia s RAM
• zložitosť TS
R
• nedeterminizmus – triedy P a NP
• redukovateľnosť, pojem úplného problému
• Cook-Lewinova veta ( o NP-úplnosti SATu)
Lineárne programovanie
D
1.2
Mnohé dôležité optimalizačné problémy sa dajú formulovať nasledujúcim spôsobom:
chceme optimalizovať (t.j. minimalizovať alebo maximalizovať) hodnotu lineárnej
funkcie n premenných, pričom hodnoty premenných musia spĺňať isté obmedzenia. V
prípade, že tieto obmedzenia sú vyjadriteľné formou lineárnych nerovností, hovoríme
o úlohe lineárneho programovania.
Príklad 1.1 Chceme nájsť minimum fukcie
f (x1 , x2 , x3 ) := 10x1 + 3x2 + 5x3
spomedzi takých hodnôt x1 , x2 , x3 , ktoré spĺňajú
6x1 + x2 − x3
≥ 2
(1.1)
2x1 + 2x2 + 6x3
≥ 8
(1.2)
6x1 + 3x2 + 5x3
=
x1 , x2 , x3
1
30
≥ 0
2
KAPITOLA 1. ÚVOD
Nech z ∗ je hľadané minimum. Horný odhad na z ∗ sa dá získať jednoduchým dosadením a overením podmienok. Napríklad ak zvolíme x = (x1 , x2 , x3 ) = (2, 6, 0),
ľahko overíme, že z ∗ ≤ 38. Ako však môžeme dokázať dolný odhad? Keď sa lepšie
pozrieme na nerovnosť (1.1), zistíme, že jej ľavá strana je po zložkách menšia ako f ,
preto určite z ∗ ≥ 2. Lepší dolný odhad získame, ak sčítame (1.1) a (1.2): dostaneme
nerovnosť
8x1 + 3x2 + 5x3 ≥ 10
ktorej ľavá strana je opäť po zložkách menšia ako f , čím sme dokázali, že z ∗ ≥ 10.
Takže na nájdenie dolného odhadu na z ∗ hľadáme lineárnu kombináciu
FT
y1 (6x1 + x2 − x3 ) + y2 (2x1 + 2x2 + 6x3 ) + y3 (6x1 + 3x2 + 5x3 )
tak, aby bola po zložkách menšia ako f . Navyše, keďže treba dodržať nerovnosti v
(1.1) a (1.2), koeficienty y1 a y2 musia byť nezáporné. Predchádzajúce úvahy môžeme opäť formulovať ako úlohu lineárneho programovania: chceme nájsť maximum
funkcie
g(y1 , y2 , y3 ) := 2y1 + 8y2 + 30y3
spomedzi takých hodnôt y1 , y2 , y3 , ktoré spĺňajú
≤
10
y1 + 2y2 + 3y3
≤
3
−y1 + 6y2 + 5y3
≤
5
y1 , y2
≥
0
R
A
6y1 + 2y2 + 6y3
´
Ak sa nám teraz podarí nájsť dva vektory x a y spňajúce
podmienky tak, že
∗
f (x) = g(y) = z znamená to, že z = z. V našom prípade môžme zvoliť x = (0, 5, 3)
a y = (0, 0, 1), čím dokážeme, že z ∗ = 30.
Úvahy z predchádzajúceho príkladu môžme formalizovať nasledovným spôsobom.
Definícia 1.1 Úloha lineárneho programovania v kánonickom tvare je nájsť
D
primárna úloha
LP
min
n
X
cj x j
j=1
za predpokladov
n
X
aij xj
≥ bi
i = 1, . . . , m
xj
≥ 0
j = 1, . . . , n
j=1
V tejto definícii vyžadujeme, aby všetky premenné boli nezáporné. Ľahko vidno,
že týmto obmedzením neustrácame na všeobecnosti: ak chceme, aby premenná xi
mohla nadobúdať aj záporné hodnoty, nahradíme ju dvoma nezápornými premen−
+
−
nými x+
i , xi a za xi substituujeme xi − xi . Rovnako podmienka, že všetky ohraničenia musia byť vyjadrené pomocou nerovností neuberá na všeobecnosti, keďže
rovnosť môžme vyjadriť dvoma nerovnosťami.
K primárnej úlohe LP definujeme duálnu úlohu:
duálna úloha LP
Nájsť
1.2. LINEÁRNE PROGRAMOVANIE
max
3
m
X
bi yi
i=1
za predpokladov
m
X
aij yi
≤ cj
j = 1, . . . , n
yi
≥ 0
i = 1, . . . , m
i=1
Úspornejší maticový zápis dvojice primárnej a duálnej úlohy je
FT
P : min{cT x | Ax ≥ b, x ≥ 0}
D : max{bT y | AT y ≤ c, y ≥ 0}
Vektor x, ktorý spĺňa Ax ≥ b, x ≥ 0 nazveme prípustné riešenie primárnej
úlohy, vektor y, pre ktorý platí AT y ≤ c, y ≥ 0 nazveme prípustným riešením
duálnej úlohy.
Ľahko vidno, že platí nasledujúci vzťah:
Dôkaz:
A
Veta 1.1 Ak x je prípustné priešenie primárnej úlohy a y je prípustné riešenie
duálnej úlohy, potom
cT x ≥ b T y
c T x ≥ AT y
T
x = y T Ax ≥ y T b
slabá veta
o dualite LP
(1.3)
R
Ak nájdeme x a y tak, že cT x = bT y, vieme, že máme optimálne riešenie
podobne ako v príklade 1.2. Dá sa to však vždy? Odpoveď je kladná a vujadruje ju
nasledujúca veta:
D
Veta 1.2 Primárna úloha LP má konečné optimum práve vtedy, keď ho má duálna
úloha. Naviac, ak x∗ , y ∗ sú príslušné optimálne riešenia primárnej, resp. duálnej
úlohy, platí
cT x∗ = bT y ∗
silná veta
o dualite LP
Čo vieme povedať a štruktúre optimálnych riešení? Podľa silnej vety o dualite
musia v (1.3) platiť všade rovnosti. Z toho dostávame nasledujúcu charakterizáciu:
Veta 1.3 Nech x, y sú prípustné riešenia primárnej a duálnej úlohy. Potom x, y
sú obidve optimálne práve vtedy, ak sú splnené obe nasledujúce podmienky:
• primárna podmienka komplementarity:
∀ 1 ≤ j ≤ n : buď xj = 0 alebo
m
X
aij yi = cj
i=1
• duálna podmienka komplementarity:
∀ 1 ≤ i ≤ m : buď yi = 0 alebo
n
X
j=1
aij xj = bi
podmienky
komplementarity
4
KAPITOLA 1. ÚVOD
Napriek tomu, že kánonický tvar LP neuberá na všeobecnosti, niekedy je príjemnejšie používať ohraničenia vo forme rovností, alebo premenné, nadobúdajúce aj
záporné hodnoty. Vzťah medzi primárnou a duálnou úlohou potom charakterizuje
nasledujúca tabuľka
primárna úloha
duálna úloha
i-te obmedzenie tvaru
j=1
n
X
i-te obmedzenie tvaru
aij xj ≥ bi
j=1
xj ∈ R
j-ta premenná
xj ≥ 0
j-ta premenná
maximalizovať
bT y
i-ta premenná
yi ∈ R
FT
cT x
n
X
aij xj = bi
minimalizovať
yi ≥ 0
i-ta premenná
j-te obmedzenie tvaru
j-te obmedzenie tvaru
m
X
i=1
m
X
aij yi = cj
aij yi ≤ cj
i=1
*** to do: riešiteľnosť LP, ILP je NP-ťažké ***
CauchySchwartz
Použité vzťahy
A
1.3
Veta 1.4 Nech a = (a1 , . . . , an ), b = (b1 , . . . , bn ) sú dve postupnosti komplexných
čísel. Potom platí
!2
!
!
n
n
n
X
X
X
2
2
ak bk
≤
ak ·
bk
k=1
k=1
k=1
resp. v skrátenej forme pomocou normy a skalárneho súčinu vektorov
Wallisov vzorec
R
|ha, bi| ≤ ||a|| · ||b||
Veta 1.5
lim
n7→∞
Veta 1.6
D
Stirlingov vzorec
√
2πn
n n
e
n
Y
2i
2i
−1
i=1
< n! <
√
!2
1
π
=
2n + 1
2
·
2πn
n n e
1+
1
12n − 1
Dôkaz: Zoberme si namiesto n! najprv log(n!). Máme
log(n!) =
n
X
log(i)
i=1
Pretože logaritmus je rastúca funkcia, dostaneme
Z i
Z i+1
log(x)dx < log(i) <
log(x)dx
i−1
i
Sčítame a dostaneme
Z
n
Z
log(x)dx < log(n! <
0
n+1
log(x)dx
1
1.3. POUŽITÉ VZŤAHY
Pretože
R
5
log xdx = x log x − x a limx7→0 x log x = limx7→0 log xx = 0, dostaneme
n log n − n < log(n!) < (n + 1) log(n + 1) − n
Teraz zvoľme
dn := log(n!) − n +
1
log n + n
Máme
Použijeme Taylorov rozvoj
1
log
2
1+t
1−t
a dostaneme
0 < dn − dn+1
1+
1−
1
2n+1
1
2n+1
!
FT
dn − dn+1
n+1
1
1
log
−1= n+
log
= n+
2
n
2
1
1
= t + t3 + t5 + · · ·
3
5
1X
1
1
1
1
<
=
=
2i
2
3 i>0 (2n + 1)
3 (2n + 1) − 1
12
1
1
−
n n+1
Odtiaľ vieme, že postupnosť dn je klesajúca a postupnosť dn − 1/12n je rastúca, a
teda obidve konvergujú k spoločnej limite C, takže
A
n!
lim
n7→∞
= eC
(1.4)
√
2π. Podľa Wallisovej formuly
!2
n
Y
1
π
2i
·
=
lim
n7→∞
2i − 1
2n + 1
2
i=1
R
Ostáva ukázať, že eC =
n(n+1/2) e−n
t.j.
2 · 4 · 6 · · · (2n)
1
√ =
lim
n7→∞ 1 · 3 · 5 · · · (2n − 1)
2n
r
π
2
a preto
D
r
(2n n!)2
1
π
lim
·√ =
n7→∞ (2n)!
2
2n
Použijeme (1.4) pre odhad faktoriálov a úpravamy dostaneme výsledok.
Definícia 1.2 n-tým harmonickým číslom Hn označujeme sumu
Hn =
n
X
i=1
1
i
Veta 1.7 Pre n-té harmonické číslo Hn platí
Hn = γ + ln n +
1
1
1
−
+
+O
2
2n 12n
120n4
1
n6
kde γ = 0.5772156649 · · · je Euler-Mascheronino konštanta.
Veta 1.8 Pre r > 1/2 platí
n
∞
X
r − 1 (r − 1)2
(r − 1)3
1 r−1
ln(r) =
+
+
+ ··· =
r
2r2
3r3
n
r
n=1
harmonické číslo
6
KAPITOLA 1. ÚVOD
Dôkaz: Nech
f (x) =
1
1−x
Indukciou sa dá ľahko ukázať, že n-tá derivácia f (x) je
f (n) (x) =
n!
(1 − x)n+1
Keďže f (x) je analytická, použijeme Taylorov rozvoj v bode a = 0 a máme
∞
∞
X
X
f (n) (a)
(x − a)n =
xn
n!
n=0
n=0
FT
f (x) =
Predpokladajme, že |x| < 1. V rovnosti
∞
X
1
=
xn
1 − x n=0
zintegrujeme obidve strany a dostávame
Zvoľme teraz
r=
t.j.
=
∞
X
xn
n
n=1
A
ln
1
1−x
1
1−x
r−1
r
a máme požadovaný výsledok. Pretože sme potrebovali, aby |x| < 1, výsledok platí
pre r > 1/2.
R
x=
1.4
náhodná
menná
pre-
Teória pravdepodobnosti
Definícia 1.3 Nech Ω je pravdepodobnostný priestor. Diskrétnou náhodnou premennou nazývame funkciu X : Ω 7→ Z.
D
Rozdelenie náhodnej premennej X je funkcia F (y) = Pr[x < y], pre −∞ <
y < ∞, takže pravdepodobnosť, že X má hodotu z intervalu hy1 , y2 i je Pr[y1 ≤ X ≤
y2 ] = F (y1 ) − F (y2 ).
Hustota pravdepodobnosti náhodnej premennej X je funkcia p : Z 7→ h0, 1i
definovaná pX (x) = P r[X = x].
Stredná hodnota
P náhodnej premennej X s hustotou pravdepodobnosti p je definovaná E[X] = x xp(x), kde sumácia sa berie cez všetky možné hodnoty X.
linearita strednej hodnoty
Veta 1.9 Nech X1 , ..., Xk sú náhodné premenné a h(X1 , ..., Xk ) je lineárna funkcia.
Potom
E[h(X1 , ..., Xk )] = h(E[X1 ], ..., E[Xk ])
Ak navyše X1 , ..., Xk sú nezávislé, platí aj
" k
#
k
Y
Y
E
Xi =
E[Xi ]
i=1
i=1
1.4. TEÓRIA PRAVDEPODOBNOSTI
Markovova
nerovnosť
7
Veta 1.10 Nech X je ľubovoľná náhodná premenná, a a ∈ R. Potom platí
P r[X ≥ a] ≤
E[X]
a
Dôkaz: Podľa definície strednej hodnoty máme
X
X
X
E[X] =
xp(x) ≥
xp(x) ≥ a
p(x) = a · P r[X ≥ a]
x
x≥a
FT
x≥a
Definícia 1.4 Diskrétna náhoná premenná X má Bernoulliho rozdelenie, ak
Bernoulliho
rozdelenie
P r[X = 1] + P r[X = 0] = 1
Veta 1.11 Majme n nezávislých náhodných premenných X1 , . . . , Xn takých, že
P r[Xk = 1] ≤ Pk pre všetky k = 1, . . . , n. Potom platí
P r[X ≥ βP ] ≤ e(1− β −ln β )βP
Pn
P
kde β > 1, X = i=1 Xi a P =
i = 1n Pi .
1
A
Dôkaz: Pri dôkaze použijeme techniku generujúcich funkcií.
Qn Uvažujme ľubovoľné
reálne číslo λ > 0 a náhodné premenné Yk = eλXk a Y = k=1 Yk = eλX . Zrejme
P r[X ≥ βP ] = P r[Y ≥ eλβP ]. Pre náhodnú premennú Yk dostaneme
E[Yk ] = E eλXk = P r[Xk = 1]eλ + 1 − P r[Xk = 1] = 1 + P r[Xk = 1](eλ − 1)
Pretože eλ > 1 a ∀x : 1 + x ≤ ex , dostávame
R
E[Yk ] ≤ 1 + Pk (eλ − 1) ≤ ePk (e
λ
−1)
Pretože Xk sú nezávislé náhodné premenné, platí
E[Y ] = E[
n
Y
k=1
Yk ] =
n
Y
E[Yk ] ≤
k=1
n
Y
ePk (e
λ
−1)
= eP (e
λ
−1)
k=1
D
Podľa Markovovej nerovnosti máme
E[Y ]
λ
P r Y ≥ eλβP ≤ λβP ≤ eP (e −1)−λβP
e
Pravá strana sa minimalizuje dosadením λ = ln β, čím máme
P r[X ≥ βP ] = P r[Y ≥ eλβP ] ≤ eP (β−1)−β ln βP = e(1− β −ln β )βP
1
*** to do: pokračovanie ***
Černovova
nerovnosť
KAPITOLA 1. ÚVOD
D
R
A
FT
8
Kapitola 2
FT
Optimalizačné problémy
V tomto texte sa budeme zaoberať optimalizačnými problémami, t.j. problémami,
v ktorých úlohou je vybrať spomedzi množiny prípustných riešení riešenie s minimálnou (resp. maximálnou) hodnotou.
optimalizačný
problém
A
Definícia 2.1 Optimalizačný problém P je štvorica (IP , SOLP , mP , cP ), kde IP je
jazyk vstupných inštancií, SOLP je funcia, ktorá každému vstupu x ∈ IP priradí
množinu prípustných riešení SOLP (x), mP je účelová funkcia, ktorá každej dvojici
x ∈ IP , y ∈ SOLP (x) priradí hodnotu riešenia mP (x, y) ∈ N, a cP je min alebo
max podľa toho, či je cieľom nájsť minimálnu alebo maximálnu hodnotu mP (x, y).
Pre dané x ∈ IP označme m∗P (x) hodnotu optimálneho riešenia, t.j.
m∗P (x) = cP {mP (x, y) | y ∈ SOLP (x)}
Ďalej označme SOL∗P (x) množinu optimálnych riešení, t.j.
SOL∗P (x) = {y | mP (x, y) = m∗P (x)}
R
Ak je problém z kontextu zrejmý, budeme vynechávať index P.
S optimalizačným problémom P môžu byť spojené rôzne úlohy podľa toho, či
chceme nájsť optimálne riešenie, alebo či sa uspokojíme iba s nájdením ceny optimálneho riešenia.
D
konštrukcia
vyhodnotenie
Pc
Pe
pre dané x ∈ I nájsť y ∈ SOL∗
pre dané x ∈ I nájsť m∗ (x)
V niektorých prípadoch budeme vynechávať index c, e; vtedy, ak nepovieme inak,
budeme uvažovať problém konštrukcie. Ako vysvitne neskôr, pre mnohé problémy,
ktoré nás budú zaujímať sú obe verzie v istom zmysle ekvivalentné. S rozhodovacím
problémom úzko súvisí pojem prislúchajúceho jazyka:
Definícia 2.2 Nech P = (I, SOL, m, c) je optimalizačný problém. Jazyk
Pd = {(x, k) | x ∈ I, m∗ (x)k}
kde je ≤ alebo ≥ podľa typu úlohy, sa nazýva jazyk prislúchajúci problému P.
2.1
Triedy Po a NPo
Našim cieľom je zaoberať sa triedami optimalizačných problémov, ktoré zodpovedajú triedam P a NP definovaným pre rozhodovacie problémy. Keďže chceme zachytiť zložitosť optimalizácie, a nie zložitosť zisťovania korektnosti vstupu, budeme
9
prislúchajúci
jazyk
10
KAPITOLA 2. OPTIMALIZAČNÉ PROBLÉMY
vyžadovať, aby vstupné inštancie boli jednoducho rozoznateľné, t.j.
IP ∈ P
(2.1)
Zároveň chceme, aby všetky prípustné riešenia boli polynomiálne veľké1 , t.j.
∃ polynóm q(·) ∀x ∈ IP ∀y ∈ SOLP (x) : |y| ≤ q(|x|)
(2.2)
trieda Po
FT
Tretia prirodzená požiadavka je, aby účelová funkcia bola vypočítateľná v polynomiálnom čase. Navrhnúť triedu zodpovedajúcu triede P je priamočiare:
Definícia 2.3 Trieda Po je trieda optimalizačných problémov (I, SOL, m, c), ktoré
spĺňajú (2.1), (2.2), a navyše existuje deterministický Turingov stroj, ktorý v polynomiálnom čase vypočíta2 pre každé x ∈ I hodnotu m∗ (x) a nejaké y ∈ SOL∗ (x).
Ostáva teda otázka, čo je ekvivalent triedy NP pre optimalizačné problémy.
Budeme požadovať, aby to boli práve tie problémy, ktorých rozhodovacie verzie
tvoria triedu NP, teda problémy, pre ktoré vieme pre daný vstup x a hodnotu k
nedeterministicky v polynomiálnom čase povedať, či existuje riešenie s hodnotou
aspoň (resp. najviac) k.
Definícia 2.4 Trieda NPo je trieda optimalizačných problémov (I, SOL, m, c), ktoré
spĺňajú (2.1), (2.2), a navyše existuje deterministický Turingov stroj, ktorý pre dané
x ∈ I a y také, že |y| ≤ q(|x|), v polynomiálnom čase zistí, či y ∈ SOL(x).
R
A
trieda NPo
Keďže rozhodovacie problémy sú špeciálnym prípadom optimalizačných, zjavne
NP ⊆ NPo . Ľahko vidno nasledovné tvrdenie:
Tvrdenie 2.1 Nech P je optimalizačný problém taký, že P ∈ NPo . Potom prislúchajúci jazyk Pd ∈ NP.
2.2
Redukovateľnosť
D
Prv než pokročíme v našich úvahách, je namieste venovať sa pojmu redukovateľnosti. Našim cieľom bude porovnávať problémy z hľadiska ich “ťažkosti”, resp. vybrať “najťažšie” problémy z danej triedy. Pri rozhodovacích problémoch sme používali pojem Karpovej (tzv. many-one) redukcie. Keďže pri rozhodovacích problémoch
existuje prirodzená bijekcia medzi problémom a jazykom tých vstupných inštancií,
na ktorých je výstupom true, budeme v ďalšom často stotožňovať rozhodovací
problém a jemu prislúchajúci jazyk, a pojem redukovateľnosti môžeme definovať na
jazykoch
Karpova
redukovateľnosť
Definícia 2.5 Jazyk A je polynomiálne redukovateľný na jazyk B, čo budeme označovať A ∝pm B, ak existuje funkcia f počítaná deterministickým Turingovým strojom
v polynomiálnom čase taká, že x ∈ A ⇔ f (x) ∈ B. Ak A ∝pm B a zároveň B ∝pm A,
budeme písať A ≡pm B.
Takto definovaná redukovateľnosť sa nedá priamočiaro použiť na optimalizačné
problémy. Jedna cesta je definovať redukovateľnosť optimalizačných problémov pomocou ich prislúchajúcich jazykov. Existuje však aj iný pojem redukovateľnosti,
ktorý sa dá priamočiaro použiť aj pre optimalizačné problémy. Táto redukovateľnosť sa označuje ako výpočtová, resp. Turingova redukovateľnosť a využíva pojem
Turingových strojov s pomocou3 .
2.3. VZŤAH MEDZI NP A NPO
Turingov stroj
s pomocou
11
Definícia 2.6 Mech g : Σ∗ 7→ Σ∗ je ľubovoľná funkcia. Turingov stroj M s pomocou
g, označovaný M (g) je Turingov stroj so špeciálnou pomocnou páskou a špeciálnymi
stavmi q? a q! . Ak v nejakom kroku výpočtu je stroj v stave q? a na pomocnej páske
je napísané slovo w, stroj prejde do stavu q! a na pomocnej páske bude napísané
slovo g(w).
Neformálne povedané, problém P1 je výpočtovo redukovateľný na problém P2 ,
ak sa P1 dá vyriešiť s pomocou podprogramu, ktorý rieši P2 .
Turingova
redukovateľnosť
FT
Definícia 2.7 Nech P1 = (I1 , SOL1 , m1 , c1 ), P2 = (I2 , SOL2 , m2 , c2 ) sú optimalizačné problémy. Nech g je funkcia, pre ktorú platí ∀x : g(x) ∈ SOL∗2 (x). Problém
P1 je polynomiálne výpočtovo redukovateľný na problém P2 , označované P1 ∝pT P2 ,
ak existuje deterministický Turingov stroj s pomocou g, ktorý v polynomiálnom čase
rieši problém P1 . Ak A ∝pT B a zároveň B ∝pT A, budeme písať A ≡pT B.
A
Ako sme spomínali, rozhodovacie problémy sú špeciálnym prípadom optimalizačných, preto aj Karpova redukovateľnosť je špeciálnym prípadom Turingovej
redukovateľnosti, kedy sa pomoc žiada iba jedenkrát, a výstup z pomocnej pásky je
výstupom celého výpočtu. Na druhej strane, Turingova redukovateľnosť sa zdá byť
silnejšia ako Karpova: zjavne každý problém v co-NP je Turingovo redukovateľný
na každý NP-úplný problém, na druhej strane problémy z co-NP−NP (ak existujú),
nemajú Karpovu redukciu na žiaden problém z NP4 .
S pomocou Turingovej redukcie môžme vybrať “najťažšie” problémy triedy NPo :
Definícia 2.8 Optimalizačný problém P = (I, SOL, m, c) je NPo -ťažký, ak pre každý
optimalizačný porblém P 0 platí P 0 ∝pT P. Ak navyše P ∈ NPo , hovoríme, že P je
NPo -úplný.
Vzťah medzi NP a NPo
R
2.3
Najprv sa zamerajme na vzťahy medzi rôznymi variantmi toho istého problému.
Veta 2.2 Nech P ∈ NPo . Potom Pd ≡pT Pe ∝pT Pc . Ak navyše Pd je NP-úplný,
potom Pc ∝pT Pd .
D
Dôkaz: Zjavne Pd ∝pT Pe ∝pT Pc . Ukážeme teraz, že Pe ∝pT Pd . Podľa definície NPo
je m vypočítateľná v polynomiálnom čase5 a každé prípustné riešenie y ∈ SOL(x)
je polynomiálne veľké (t.j. |y| ≤ (|x|)). Teda maximálna hodnota m(x, y) pre dané
x je zhora ohraničená 2p(|x|) pre nejaký polynóm p. Preto ak máme k dispozícii
podprogram pre Pd , môžme pomocou binárneho vyhľadávania vyriešiť problém Pe
v čase log 2p(|x|) = p(|x|).
Nech teraz Pd je NP-úplný. Ukážeme, ako riešiť Pc s podprogramom Pd . Modifikujme problém P tak, že do ceny riešenia zakódujeme aj samotné riešenie. Formálne, zostrojme problém P 0 , ktorý bude identický s problémom P, ale účelová
funkcia bude
mP 0 (x, y) = 2q(|x|)+1 mP (x, y) + λ(y)
1 ináč by už samotné zapísanie riešenia na pásku Turingovho stroja vyžadovalo viac ako polynomiálne veľa operácií
2 Počítanie deterministického Turingovho stroja A môžme definovať nasledovne: stroj A počíta
na vstupnom slove w prirodzené číslo x, ak zastaví v konfigurácii, v ktorej je na začiatku pásky
zapísané x v binárnom zápise a zvyšok pásky je prázdny.
3 oracle Turing machines
4 pretože NP je uzavretá na Karpovu redukovateľnosť
5 vzhľadom na veľkosť vstupu
NPo -úplnosť
12
KAPITOLA 2. OPTIMALIZAČNÉ PROBLÉMY
kde q je polynóm ohraničujúci dĺžku riešenia a λ(y) je poradové číslo reťazca y v
lexikografickom usporiadaní. Zjavne problém P 0 má jednoznačné riešenie, a navyše
mP 0 je zjemnením mP 0 v tom zmysle, že
mP 0 (x, y1 ) > mP 0 (x, y2 ) ⇒ mP (x, y1 ) ≥ m0P (x, y2 )
Preto optimálne riešenie P 0 je aj optimálnym riešením P. Navyše, z ceny optimálneho riešenia P 0 vieme optimálne riešenie P jednoducho získať. S využitím prvej
časti vety a NP-úplnosti Pd preto dostávame
FT
Pc ∝pT Pe0 ∝pT Pd0 ∝P
m Pd
Ako sme spomínali, našim cieľom je skúmať riešiteľnosť problémov, o ktorých
sme presvedčení, že sú ťažké, t.j. problémov, ktorých rozhodovacie verzie sú NPúplné. Keďže ale Turingova redukovateľnosť je silnejšia ako Karpova, mohla by
nastať situácia, že problém, ktorého rozhodovacia verzia je NP-úplná (v zmysle
Karpovej redukovateľnosti), a teda je považovaný za ťažký, je Turingovo redukovateľný na ľahký problém. Ako vidno z nasledujúcej vety, takáto situácia nenastáva a
ťažké problémy ostávajú ťažkými aj v zmysle Turingovej redukovateľnosti.
Veta 2.3 Ak Pd je NP-úplný, tak Pc je NPo -ťažký.
A
Dôkaz: Treba ukázať, že pre ľubovoľný Pc0 ∈ NPo platí Pc0 ∝pT Pc . Podobne ako v
dôkaze Vety 2.2 zostrojíme problém P 00 pre ktorý platí Pc0 ∝pT Pe00 . Podľa Vety 2.2
potom Pe00 ∝pT Pd00 . Pretože Pd je NP-úplný, Pd00 ∝pm Pd . Takže máme
Pc0 ∝pT Pe00 ∝pT Pd00 ∝pm Pd ∝pT Pc
R
Prečo neplatí, že Pc je NPo -úplný? dôvod je ten, že nemusí byť v NPo : zoberme
ľubovoľný minimalizačný NPo -úplný problém a doplňme ku každému vstupu x jedno
prípustné riešenie yx ∈ SOL(x) exponenciálnej dĺžky. Dodefinujme m(x, yx ) = ∞.
Zjavne pre takto upravený problém Pd je NP-úplný, pretože dodané prípustné riešenia nikdy nie sú optimálne. Úvahy v tejto kapitole môžme zhrnúť takto:
D
Optimalizačné problémy z triedy NPo , ktorých rozhodovacie verzie sú NP-úplné
(t.j. tie, ktoré nás budú zaujímať v tomto texte) sú NPo -ťažké a všetky ich varianty
(konštrukčná, vyhodnocovacia, rozhodovacia) sú navzájom Turingovo ekvivalentné.
Na záver posledné pozorovanie:
Dôsledok 2.4 Ak P 6= NP, potom Po 6= NPo .
Dôkaz: Nech Po = NPo . Zoberme problém P ∈ NPo taký, že Pd je NP-úplný.
Potom Pc je NPo -ťažký, takže špeciálne každý problém P 0 ∈ NP je P 0 ∝pT Pc . Lenže
pre Pc existuje deterministický Turingov stroj, ktorý ho počíta, lebo Po = NPo .
Takže máme P = NP.
2.4
aproximačný
algoritmus
Aproximácia
Definícia 2.9 Majme daný optimalizačný problém P = (I, SOL, m, c). Algoritmus
A je aproximačný algoritmus pre problém P, ak pre každú vstupnú inštanciu x ∈ I
platí A(x) ∈ SOL(x).
2.4. APROXIMÁCIA
13
Z hľadiska tejto definície je aproximačný algoritmus ľubovoľný algoritmus, ktorý
pre daný vstup nájde akékoľvek prípustné riešenie. Pochopiteľne, toto samo osebe
nezodpovedá intuitívnej predstave aproximácie – cieľom je mať algoritmy, ktoré
vrátia riešenie “dostatočne blízko” optimálnemu. Preto meradlom kvality aproximačných algoritmov je, ako ďaleko je hodnota dosiahnutého riešenia od optimálnej
hodnoty. V nasledujúcej časti sa pozrieme do sveta ťažkých problémov (takých, ktorých rozhodovacie verzie sú NP-úplné) a predstavíme v rámci nich hierarchiu podľa
kvality aproximácie.
Absolútna aproximácia
FT
2.4.1
Definícia 2.10 Majme daný optimalizačný problém P, inštanciu x ∈ I a riešenie
y ∈ SOL(x). Absolútnou chybou y nazveme
absolútna
aproximácia
D(x, y) = |m∗ (x) − m(x, y)|
Aproximačný algoritmus A nazveme k-absolútny, ak existuje konštanta k taká, že
∀x ∈ I platí D (x, A(x)) ≤ k.
Je iba veľmi málo problémov, pre ktoré existuje absolútna aproximácia.
A
Príklad 2.1 Uvažujme problém minimálneho vrcholového farbenia planárneho
grafu. Z vety o 4 farbách vyplýva, že optimálne riešenie je najviac 4. Z Haewoodovej
vety dostávame polynomiálny algoritmus, ktorý nájde 5-farbenie.
farbenie
planárneho
grafu
Uvažujme teraz známy “problém batohu”: z daného zoznamu vecí treba vybrať
niekoľko do batoha tak, aby cena vybratých vecí bola čo najväčšia.
Definícia 2.11 Na vstupe je dané prirodzené číslo b a n vecí, pričom P
i-ta vec má
objem vi ≤P
b a cenu ci . Úlohou je nájsť množinu I ⊆ {1, . . . , n} takú, že i∈I vi ≤ b
a zároveň i∈I ci je maximálna možná.
Knapsack
R
Problém Knapsack je NP-úplný.
Veta 2.5 Ak P 6= NP, potom pre problém Knapsack neexisuje absolútny algoritmus.
D
Dôkaz: Sporom. Nech existuje algoritmus A, pre ktorý D(x, y) < k. Ukážeme, že
potom existuje polynomiálny algoritmus pre Knapsack. Pre daný vstup X s cenami
ci a objemami vi vyrobíme nový vstup X 0 s cenami ci a objamami vi0 := (k + 1)vi a
spustíme A na vstupe V 0 . Keďže vi0 sú násobky k + 1, aj cena ľubovoľného riešenia
je násobok k + 1, a teda A dá optimálne riešenie vstupu X 0 . Zjavne ale toto riešenie
je aj optimálnym riešením pre X.
2.4.2
Relatívna aproximácia – trieda APX
Keďže teda sú problémy, pre ktoré neexistuje algoritmus s konštantnou chybou, zvoľnime svoje požiadavky tak, že budeme uvažovať chybu normovanú podľa výslednej
hodnoty:
Definícia 2.12 Majme daný optimalizačný problém P, inštanciu x ∈ I a riešenie
y ∈ SOL(x). Relatívnou chybou y nazveme
E(x, y) =
D(x, y)
max{m(x, y), m∗ (x)}
Aproximačný algoritmus A nazveme ε-relatívny, ak existuje konštanta ε taká, že
∀x ∈ I platí E (x, A(x)) ≤ ε.
relatívna
aproximácia
14
KAPITOLA 2. OPTIMALIZAČNÉ PROBLÉMY
Namiesto ε-realtívny aproximačný algoritmus budeme skrátene hovoriť ε-aproximačný
algoritmus.
Podľa predchádzajúcej definície je relatívna chyba pre minimalizačné problémy
E(x, y) =
m(x, y) − m∗ (x)
m∗ (x)
=1−
m(x, y)
m(x, y)
a pre maximalizačné problémy
E(x, y) =
m∗ (x) − m(x, y)
m(x, y)
=1− ∗
m∗ (x)
m (x)
m(x,y)
m∗ (x)
FT
Namiesto relatívnej chyby budeme často pracovať s pomerom R(x, y) =
∗
m (x)
(pre minimalizačné problémy), resp. R(x, y) = m(x,y)
(pre maximalizačné problémy). Túto hodnotu, t.j.
1
R(x, y) =
1 − E(x, y)
budeme označovať aproximačný pomer a udáva, koľkokrát je výstup algoritmu horší
ako optimálne riešenie. Algoritmus, ktorý má na každom vstupe aproximačný pomer
najviac r budeme volať r-aproximačný algoritmus6 .
Príklad 2.2 Uvažujme problém Kapscak. Na začiatok si vezmime jeho racionálnu
verziu, t.j. verziu, pri ktorej je možné jednotlivé veci deliť, takže je možné do batoha
dať ľubovoľnú časť z danej veci7 . V tomto prípade je riešenie jednoduché – stačí
utriediť veci podľa relatívnej ceny (t.j. podľa pomeru ci /vi ) a postupovať greedy
spôsobom, t.j. brať zaradom veci kým sa zmestia do batoha a z prvej veci ktorá sa
nezmestí zobrať príslušnú časť tak, aby sa batoh zaplnil.8 Skúsme teraz použiť ten
istý greedy algoritmus na celočíselnú verziu: utriedime si veci podľa relatívnej ceny,
a kým sa zmestia, pridávame ich do batoha. Vieme ohraničiť aproximačný pomer
tohoto algoritmu konštantou? Odpoveď je záporná: pre ľubovoľné r vieme zostrojiť
vstup, na ktorom je greedy algoritmus aspoň r-krát horší ako optimum. Vstup bude
mať n vecí, pričom veľkosť batoha bude b = rn. Prvých n − 1 vecí bude mať objem
aj cenu 1, n-tá vec bude mať objem vn = b a cenu cn = b − 1. Optimálne riešenie
má cenu rn − 1, ale greedy algoritmus naplní batoh n − 1 vecami s jednotkovou
cenou, taže vráti riešenie s cenou n − 1. Upravme teda greedy algoritmus tak, že
ak je výsledné riešenie menšie ako najcennejšia vec, algoritmus vráti najdrahšiu vec
(Algoritmus 1)
Ukážeme, že takto upravený algoritmus je 2-aproximačný, t.j. že pre každý
vstup je pomer m∗ /m < 2, kde m∗ označuje cenu optimálneho riešenia a m cenu
riešenia
nájdeného algoritmom. Nech j je index prvej nevybratej veci; označme
Pj−1
cj = k=1 ck . Ako sme už ukázali, optimálne riešenie racionálnej verzie má hodnotu cj + αcj pre nejaké 0 ≤ α < 1. Keďže ale racionálna verzia obsahuje celočíselnú
verziu ako špeciálny prípad, platí m∗ ≤ cj + αcj ≤ cj + cj . Rozlíšime 2 prípady:
D
R
2-aproximačný
knapsack
Definícia 2.13 Trieda APX je trieda problémov, pre ktoré existuje polynomiálny
r-aproximačný algoritmus pre nejakú konštantu r.
A
trieda APX
6 Keďže relatívna chyba ε je vždy 0 ≤ ε ≤ 1, kým aproximačný pomer r je vždy r ≥ 1, je pojem
x-aproximačný algoritmus dobre definovaný – algoritmus s konštantnou relatívnou chybou má aj
konštantný aproximačný pomer a navyše je z kontextu zrejmé, či x označuje relatívnu chybu alebo
aproximačný pomer.
7 formálne povedané, na vstupe je dané prirodzené číslo b a n vecí, pričom i-ta vec má objem
P
vi a cenuPci . Úlohou je nájsť vektor x = (x1 , . . . , xn ), kde 0 ≤ xi ≤ 1 taký, že n
i=1 xi vi ≤ b a
zároveň n
x
c
je
maximálna
možná.
i=1 i i
8 Prečo je tento algoritmus optimálny? Zoberme ľubovoľné iné riešenie x. Potom existuje kus
nejakej veci, nazvime ho A, ktorý je vybratý greedy algoritmom a nevybratý v x. Lenže z toho,
ako bol greedy algoritmus konštruovaný vyplýva, že miesto, ktoré zaberalo A v greedy riešení je v
x zabraté nejakou lacnejšou vecou B. Takže keď vymeníme B za A v x, dostaneme lepšie riešenie.
2.4. APROXIMÁCIA
15
FT
Algoritmus 1 2-aproximačný algoritmus pre problém Knapsack
1: vstup: číslo b a n vecí x1 , ..., xn s objemami vi ≤ b a cenami ci
2: majme veci utriedené podľa ci /vi
3: nech xmax je vec s maximálnou cenou
4: I := ∅; i := 1
P
5: while
j∈I vj < b do
6:
I := I ∪ {xi }; i := i + 1
7: end while
P
8: if
j∈I cj > cmax then vráť I else vráť {xmax }
• Ak cj ≤ cj ≤ cmax , máme m∗ ≤ 2cmax ≤ 2m
• Ak cj > cj , máme m∗ < 2cj ≤ 2m
2.4.3
Lepšie ako APX: PTAS a FPTAS
A
Je trieda APX dobrým popisom problémov, ktoré sú efektívne aproximovateľné?
Nie celkom, pretože príslušnosť do triedy APX zaručuje iba existenciu konštanty,
ohraničujúcej aproximačný pomer. Táto konštanta však môže byť ľubovoľne veľká,
čo môže znamenať, že príslušný algoritmus je pre praktické účely nepoužiteľný.
Hodnotnejší výsledok je, ak existuje r-aproximačný algoritmus pre každé r > 1:
Definícia 2.14 Trieda PTAS9 zahŕňa problémy, pre ktoré existuje aproximačná
schéma. Aproximačná schéma je algoritmus A, ktorý pre ľubovoľný vstup x a ľubovoľné r > 1 vráti riešenie s relatívnou chybou
R
E(x, A(x, r)) ≤ 1 −
trieda PTAS
1
r
v čase polynomiálnom od veľkosti vstupu |x|.
Príkladom problému, pre ktorý existuje PTAS je problém rovnomerného rozdelenia množiny vecí:
D
Definícia 2.15 Na vstupe je daných n prirodzených čísel x = (x1 , . . . , xn ). Úlohou
je nájsť rozklad Y množiny {1, . . . , n} na dve dizjunktné množiny Y1 , Y2 tak, aby
cena
(
)
X
X
m(x, Y) = max
xi ,
xi
i∈Y1
Min-Partition
i∈Y2
bola najmenšia možná.
Príklad 2.3 Bez ujmy na všeobecnosti predpokladajme, že r < 2 (inak stačí vrátiť
prázdnu množinu). Idea algoritmu spočíva v tom, že veľké čísla sú “dôležitejšie”,
pretože chyba pri ich umiestnení sa ťažšie napráva. Preto sa prvých k najväčších čísel
snažíme rozdeliť presne. Zyšné čísla doplníme jednoduchou greedy metódou dúfajúc,
že sa tým veľa nepokazí. Greedy metóda spočíva v tom, že postupne prechádzame
cez čísla od najväčšieho po najmenšie a pridávame ich k tej množine, ktorá je
momentálne menšia. Číslo k treba zvoliť tak, aby sa optimálne riešenie pre prvých
k čísel dalo nájsť v polynomiálnom čase.
9 polynomial-time
approximation scheme
PTAS pre MinPartition
16
KAPITOLA 2. OPTIMALIZAČNÉ PROBLÉMY
Algoritmus 2 PTAS pre problém Min-Partition
1: vstup:
l čísla
m x = (x1 , . . . , xn ), utriedené zostupne, a 1 < r < 2
2−r
r−1
2:
k :=
3:
4:
5:
nájdi optimálne riešenie Y1 , Y2 pre x0 = (x1 , . . . , xk )
for i = k + 1 to n do
P
pridaj i do množiny Yk s menšou hodnotou
xj
6:
end for
j∈Yk
FT
Krok 3 sa dá riešiť prehľadaním všetkých možností v čase O(2k ), čo je pre
konštantné r konštanta, preto celý algoritmus pracuje v polynomiálnom čase. Ostáva
nám
r-aproximačný. Zaveďme najprv niekoľko označení. Nech W1 =
P ukázať, že je P
x
a
W
=
2
j∈Y1 j
j∈Y2 xj . Bez ujmy na všeobecnosti predpokladajme W1 > W2 .
Ďalej nech L = (W1 + W2 )/2, t.j. L je dolné ohraničenie optimálneho riešenia pre
prípad, že sa množina dá rozdeliť na dve presne rovnaké časti. Nech h je index
prvku, ktorý bol posledne pridaný do Y . Ak h < k ľahko vidno, že algoritmus vrátil
optimálne riešenie: W1 je totiž optimálna hodnota pre podporoblém daného vstupu
a preto je dolným ohraničením každého riešenia celého vstupu. Nech teda h ≥ k.
Zjavne W1 − xh ≤ W2 , pretože v okamihu, keď sa položil prvok h do Y1 bola Y1
menšia ako Y2 a potom už pribúdali prvky iba do Y2 . Teda platí
xh
≤L
2
A
W1 −
Odhadnime teraz aproximačný pomer:
L + x2h
W1
xh
xh
W1
≤
≤
=1+
≤1+
≤r
∗
m (x)
L
L
2L
xh (k + 1)
R
Predposledná nerovnosť vyplýva z nasledujúceho pozorovania: keďže h ≥ k, existuje
aspoň k + 1 prvkov veľkosti aspoň xh . Lenže 2L je súče všetkých prvkov, preto
2L ≥ xh (k + 1).
D
Dá sa povedať, že problémy v triede PTAS vieme aproximovať s ľubovoľnou presnosťou v polynomiálnom čase. Má to však jeden háčik. Pre ľubovoľnú konštantnú
presnosť síce existuje polynomiálny algoritmus, ale stupeň tohto polynómu môže s
rastúcou presnosťou exponenciálne rásť, takže za istou hranicou presnosti už aproximácia nie je efektívne vypočítateľná. Preto pojem PTAS zjemníme nasledovne
trieda FPTAS
Definícia 2.16 Trieda FPTAS10 zahŕňa problémy, pre ktoré existuje polynomiálna
aproximačná schéma, t.j algoritmus A, ktorý pre ľubovoľný vstup x a ľubovoľné r > 1
vráti riešenie s relatívnou chybou
E(x, A(x, r)) ≤ 1 −
1
r
v čase polynomiálnom od veľkosti vstupu |x| a od hodnoty
FPTAS
pre
Knapsack
1
r−1 .
Príklad 2.4 Vezmime si opäť problém batoha. Naším cieľom je ukázať, že preňho
existuje FPTAS. Uvažujme nasledujúci algoritmus, ktorý rieši problém batoha optimálne pomocou dynamického programovania. Majme dvojrozmernú tabuľku M ,
ktorej políčko M [k, p] ⊆ {1, . . . , k} obsahuje výber spomedzi prvých k vecí, ktorý
10 fully
polynomial-time approximation scheme
2.4. APROXIMÁCIA
17
P
P
má cenu práve p11 , t.j. vyžadujeme, aby i∈M [k,p] vi ≤ b a i∈M [k,p] ci = p. Prvý
stĺpec tabuľky M [1, p] sa inicializuje ľahko – je to buď ∅ alebo {1}, ak p = c1 . Ďalšie stĺpce sa vypĺňajú podľa nasledovného vzorca (S[k, p] je celkový objem vecí v
políčku M [k, p] alebo ∞ ak M [k, p] = ∅):

M [k − 1, p − ck ] ∪ {k} ak p ≥ ck a M [k − 1, p − ck ] 6= ∅ a



S[k − 1, p − ck ] + vk ≤ b a
M [k, p] =
S[k − 1, p − ck ] + vk ≤ S[k − 1, p]



M [k − 1, p]
inak
FT
Zjavne pre nájdenie optimálneho riešenia stačí prehľadať posledný stĺpec tabuľky M [n, p] a navyše celý algoritmus pracuje v čase polynomiálnom od rozmerov tabuľky. Pravda, tieto rozmery nie sú polynomiálne od
vstupu: počet
Pveľkosti
n
riadkov tabuľky zodpovedá maximálnej možnej cene, t.j. i=1 ci , ktorá môže byť
exponenciálna od veľkosti vstupu12 . Pre naše účely využijeme tento algoritmus; aby
sme však dosiahli polynomiálny čas, spustíme ho na vstupe s naškálovanými cenami
(viď Algoritmus 3)
A
Algoritmus 3 FPTAS pre problém Knapsack
j
k
cmax (r−1)
1: T :=
n
c 2: naškáluj vstup tak, že ci := Ti
3: nájdi riešenie dynamickým programovaním
R
Akej veľkej chyby sme sa dopustili? Optimálne riešenie by sa zrejme nezmenilo,
keby sme naškálované ceny prenásobili hodnotou T . Zoberme si takto naškálovaný
a prenásobený problém. Každá vec je môže byť o niečo lacnejšia, ako v pôvodnom
vstupe, avšak najviac o T . Pretože každé riešenie pôvodného problému (t.j. každý
výber vecí, ktorý sa zmestí do batoha) je zároveň riešením modifikovaného problému
a naopak13 , dynamickým programovaním najdeme riešenie s cenou m, pre ktorú
m∗ − m ≤ nT , kde m∗ je cena optimálneho riešenia. Preto dostaneme
m∗ − m
nT
≤
m
cmax
a odtiaľ
nT + cmax
m∗
≤
≤r
m
cmax
D
Navyše počet riadkov tabuľky je najviac
ncmax
n2
≤
T
r−1
preto celý algoritmus pracuje v čase polynomiálnom od n a 1/(r − 1), a teda je
FPTAS.
2.4.4
Horšie ako APX
V predchádzajúcej časti sme sa dopracovali k triede PTAS ako ku kandidátovi na definíciu “efektívne riešiteľných” problémov. V tejto časti si ukážeme naopak príklady
11 ak taký výber neexistuje, je M [k, p] = ∅, ak ich existuje viac, vyberieme ten s minimálnym
objemom
12 takýto algoritmus sa nazýva pseudopolynomiálny algoritmus
13 nemenili sme objemy, iba ceny
18
KAPITOLA 2. OPTIMALIZAČNÉ PROBLÉMY
problémov, ktoré sú aproximovateľné, ale aproximačný pomer nie je konštantný,
ako vyžaduje definícia triedy APX, ale závisí od veľkosti vstupu. Tak, ako sme v
triede APX hovorili o r-aproximačných algoritmoch pre nejakú konštantu r, môžme
prirodzeným spôsobom rozšíriť našu definíciu aproximovateľnosti a hovoriť o f (n)aproximovateľných, či O(f (n))-aproximovateľných problémoch. Ukážeme si teraz
dva príklady takýchto problémov. Prvým príkladom je (bln nc + 1)-aproximačný
algoritmus pre problém Min-Set-Cover.
Problém Min-Set-Cover
Definícia 2.17 Na vstupe je daná množina S a množina m množín C = {C1 , . . . , Cm },
pričom Ci ⊆ S. Úlohou je vybrať množinu C 0 ⊆ C tak, aby pokrývala všetky prvky
S, t.j. aby ∀i ∈ S ∃C ∈ C 0 : i ∈ C, a zároveň aby |C 0 | bola minimálna.
FT
Min-SetCover
Nájdeme (bln nc+1)-aproximačný algoritmus pre Min-Set-Cover, kde n = |S|.
Uvažujme greedy algoritmus, ktorý vždy vyberie najväčšiu množinu a jej prvky
odstáni (viď. Algoritmus 4)
A
Algoritmus 4 (bln nc + 1)-aproximačný algoritmus pre Min-Set-Cover
1: vstup: C = {C1 , . . . , Cm }, Ci ⊆ S
2: U := S, C 0 = ∅, ∀Ci ∈ C : Xi := Ci
3: while U 6= ∅ do
4:
nech Xj je najväčšia množina spomedzi X1 , . . . , Xm
5:
C 0 := C 0 ∪ {Cj }
6:
U := U − Xj
7:
∀Xi : Xi := Xi − Xj
8: end while
9: return C 0
R
Ukážeme, že Algoritmus 4 je (bln nc + 1)-aproximačný.
*** to do: tento dôkaz je zbytočne technický, treba ho nahradiť jednoduchším ***
Nech C ∗ je optimálne riešenie a C 0 je riešenie, ktoré vráti Algoritmus 4. Stačí
nám ukázať nasledujúce tvrdenie:
X
H(|Ci |) ≥ |C 0 |
(2.3)
Ci ∈C ∗
D
kde H(n) je n-té harmonické číslo. Z (2.3) totiž priamo vyplýva, že
X
|C 0 | ≤
H(|Ci |) ≤ |C ∗ | · H(n) ≤ (bln nc + 1) |C ∗ |
Ci ∈C ∗
Nech a1 , a2 , . . . , a|C 0 | sú indexy množín v poradí, v akom ich Algoritmus 4 vyberal. Označme Cij zvyšok z množiny Ci po j − 1 krokoch, t.j. pred vybratím množiny
Caj (platí Ci1 = Ci ).
Pozrime sa teraz na prvky nejakej množiny Ci , ktoré boli prvýkrát pokryté v
j-tom kroku, t.j. prvky Ci ∩ Caj j . Z obrázka 2.1 je zrejmé, že
Ci ∩ Caj j = Cij ∩ Caj j = Cij − Cij+1
(2.4)
Tvrdenie (2.3) dokážeme v dvoch krokoch. Najprv dokážeme, že
0
∀i : H(|Ci |) ≥
|C |
X
|Cij ∩ Caj j |
j=1
|Caj j |
(2.5)
2.4. APROXIMÁCIA
19
0000000000000000
Cij 1111111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
Cajj
00000000000000
11111111111111
0000000000000000
1111111111111111
FT
00000000000000
11111111111111
1111111111111111
0000000000000000
00000000000000
11111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
00000000000000
11111111111111
0000000000000000
1111111111111111
Obr. 2.1: Časť množiny Ci , ktorú prvýkrát pokryla množina Caj .
a potom
0
|C |
X X
|Cij ∩ Caj j |
00
∀ pokrytie C :
|Caj j |
Ci ∈C 00 j=1
≥ |C 0 |
(2.6)
dôkaz (2.5)
Zvoľme pevné i. Nech li je maximálny taký index, že |Cili | > 0. Pretože Caj j bola
Algoritmom 4 vybratá ako najväčšia množina,podľa (2.4) máme
0
0
j=1
=
|Caj j |
|C |
X
|C j | − |C j+1 |
li
X
|C j | − |C j+1 |
A
|C |
X
|Cij ∩ Caj j |
i
i
≤
|Caj j |
j=1
i
i
|Cij |
j=1
=
li
X
|Cij |
X
j=1 k=|C j+1 |+1
i
1
|Cij |
Vnútornú sumu ďalej upravíme
|Cij |
|Cij |−|Cij+1 |
1
|Cij |−|Cij+1 |
≤
X
k=1
=
|Cij |
k=|Cij+1 |+1
X
1
R
X
|Cij |
k=1
1
|Cij+1 |
+k
= H |Cij | −H |Cij+1 |
Preto dostávame
0
|C |
X
|Cij ∩ Caj j |
j=1
|Caj j |
≤
li h
X
i
H(|Cij |) − H(|Cij+1 |) = H |Ci1 | − H |Cili +1 | = H |Ci1 |
j=1
D
dôkaz (2.6)
Ľavú stranu upravíme:
0
|C |
X X
|Cij ∩ Caj j |
Ci
∈C 00
j=1
|Caj j |
0
=
|C |
X
1
X
j
j=1 |Caj | Ci ∈C 00
|Cij ∩ Caj j |
Zoberme si prvky z množiny Caj j . Pretože C 00 je pokrytie, každý prvok z Caj j je
zahrnutý aspoň v jednej množine Ci ∈ C 00 . Preto
0
|C |
X
j=1
0
1
X
|Caj j | Ci ∈C 00
|Cij
∩
Caj j |
≥
|C |
X
|Caj j |
j=1
|Caj j |
= |C 0 |
Problém vrcholového farbenia
Druhým príkladom je O(n/ log n)-aproximačný algoritmus pre problém vrcholového
farbenia grafov.
20
KAPITOLA 2. OPTIMALIZAČNÉ PROBLÉMY
Uvažujme vrcholovo k-zafarbiteľný graf s n vrcholmi. Nájdeme algoritmus, ktorý
ho v polynomiálnom čase ofarbí použitím najviac log3n n farieb. Idea algoritmu je
k
jednoduchá: nájdeme čo najväčšiu nezávislú množinu vrcholov, ofarbíme ich jednou
farbou, odstránime ich z grafu a celý proces opakujeme. Na nájdenie nezávislej
množiny použijeme jednoduchý greedy algoritmus: vyberme vrchol minimálneho
stupňa, ofarbime ho a odstráňme ho aj so všetkými susedmi z grafu.
Algoritmus 5 O
7:
8:
9:
10:
n
logk n
-aproximačný algoritmus pre vrcholové farbenie
vstup: graf G = (V, E)
f := 0, U := V
while U 6= 0 do
f := f + 1, W := U
while W 6= 0 do
nech H je graf indukovaný W , a v je vrchol s minimálnym stupňom v H
ofarbi v farbou f
W := W \ {v} \ N eighH (v)
end while
end while
FT
1:
2:
3:
4:
5:
6:
R
A
Najprv ukážeme, že pre každú farbu i sa vo vnútornom while cykle ofarbí
aspoň dlogk |W |e vrcholov farbou i, t.j. že vnútorný cyklus urobí aspoň dlogk |W |e
iterácií. Keďže H je k-zafarbiteľný14 , určite má nejakú nezávislú množinu s aspoň
|W |/k vrcholmi15 . Každý vrchol tejto množiny má stupeň najviac |W | − |W |/k,
preto vieme, že v má stupeň najviac |W | k−1
k , a teda na konci iterácie ostane aspoň
k−1
|W | − |W | k = |W |/k vrcholov. Takže počet iterácií vnútorného cyklu je aspoň
dlogk |W |e.
Teraz ukážeme, že celý algoritmus potrebuje najviac log3n n farieb. Zoberme si
k
množinu U na začiatku vnútornej iterácie. Ak |U | ≤ logn n môžme na každý vrchol
k
rátať samostatnú farbu. Nech teda |U | > logn n Potom ale
dlogk |U |e ≥ logk
k
n
logk n
> logk
√ 1
n = logk n
2
Preto vieme, že vo vnútornom cykle zafarbíme aspoň
najviac log2n n iterácií vonkajšieho cyklu.
1
2
logk n vrcholov, a teda bude
D
k
2.4.5
Asymptotická aproximácia
Skúmajme najprv aproximačné algoritmy pre problém Bin-Packing.
Bin-Packing
Definícia 2.18 Na vstupe je daných n racionálnych čísel a1 , . . . , an , ai ∈ (0, 1i.
Cieľom je rozdeliť
P ich do množín B1 , . . . , Bm tak, aby ∪i Bi = {a1 , . . . , an }, pre
každé Bi platilo aj ∈Bi aj ≤ 1 a počet množín m bol minimálny.
Jednoduchý greedy algoritmus pracuje tak, že sekvenčne spracováva veci zo
vstupu a umiestňuje ich do krabice. Ak sa uvažovaná vec do aktuálnej krabice nezmestí, zoberie novú krabicu.
Pn Ľahko vidno, že takýto algoritmus je 2-aproximačný.
Keď totiž označíme A = i=1 ai , zjavne m∗ ≥ dAe. Na druhej strane m ≤ d2Ae:
uvažujme dve po sebe idúce krabice v greedy riešení. Algoritmus vybral druhú krabicu, pretože aktuálna vec sa do tej prvej už nezmestila. Preto súčet vecí v dvoch
po sebe idúcich krabiciach je aspoň 1.
14 lebo
pôvodný graf G bol tiež
vrcholov jednej farby z optimálneho ofarbenia
15 množina
2.4. APROXIMÁCIA
21
Rovnako ľahko vidieť, že aproximačný pomer tohto algoritmu sa zlepšiť nedá.
Zoberme postupnosť 4n vecí s objemami 1/2, 1/2n, 1/2, 1/2n, . . . , 1/2, 1/2n. Optimálne riešenie je použiť n krabíc na 2n vecí veľkosti 1/2 a jednu krabicu na zvyšné
veci. Algoritmus ale použije 2n krabíc.
*** to do: FirstFit: m ≤ 1.7m∗ + 2 ***
Výhodou uvedených algoritmov je, že sú tzv. online
*** to do: online algoritmy ***
Ak nepotrebujeme, aby algoritmus pracoval online, môžme algoritmus vylepšiť
(Algoritmus 6).
FT
Algoritmus 6 FirstFit Decreasing pre Bin Packing
1: vstup: n racionálnych čísel a1 , . . . , an , ai ∈ (0, 1i
2: výstup: rozdelenie čísel do m množín B1 , . . . , Bm
3: utrieď čísla tak, aby t1 ≥ t2 ≥ · · · ≥ tn
4: for i := 1, . . . , n do
5:
priraď ai do prvej množiny Bj , do ktorej sa zmestí
6:
ak taká neexistuje, pridaj novú
7: end for
Veta 2.6 Algoritmus 6 vráti pre každý vstup riešenie, pre ktoré m ≤ 1.5m∗ + 1.
R
A
Dôkaz: Veci, pre ktoré ai < 1/3 nazvime malé, ostatné veľké. Ak v riešení algoritmu
existuje krabica, ktorá obsahuje iba malé veci, potom najviac jedna (posledná)
krabica je zaplnená do menej ako 2/3.
Ak je v každej krabici aspoň jedna veľká vec, uvažujme vstup bez malých vecí a
ukážeme, že algoritmus dá optimálne riešenie. Zjavne veci väčšie ako 2/3 musia byť
v samostatnej krabici, a teda ich netreba ďalej uvažovať. Naviac, v každej krabici
sú najviac dve veci.
*** to do: podrobnejšie ***
Poznámka:
tesný.
Lepšou analýzou sa dá ukázať m ≤ 11/9m∗ + 4, a tento odhad je
D
Podľa formálnej definície aproximačného algoritmu, Algoritmus 6 nie je 1.5aproximačný. S rastúcou hodnotou optimálneho riešenia sa ale jeho aproximačný
pomer blíži k 1.5. Preto sa zvykne zavádzať pojem asymptotickej aproximácie:
Definícia 2.19 Majme daný optimalizačný problém P, inštanciu x ∈ I a riešenie
y ∈ SOL(x). Aproximačný algoritmus A nazveme asymptoicky r-aproximačný, ak
∗
(x)+c
existú konštanty r a c také, že ∀x ∈ I platí E (x, A(x)) ≤ (r−1)m
rm∗ (x)+c .
Inými slovami, asymptoticky
r-aproximačný
algoritmus je algoritmus, ktorého
1
aproximačný pomer je r + O m∗ (x) . Posobne sa dá definovať asymptotický PTAS
ako schéma, v ktorej pre akžé r existuje asymptoticky r-aproximačný algoritmus.
Predchádzajúci výsledok teda môžme interpertovať tak, že existuje asymptoticky
1.5-aproximačný algoritmus pre problém Bin Packing. Teraz dokážeme silnejšie
tvrdenie, a síce, že pre problém Bin Packing existuje asymptotický PTAS.
Intuitívne, najdôležitejšie je umiestniť veľké veci, lebo pri nich môžu vznikať
veľké chyby. Náš algoritmus preto naprv zruší malé veci, vyrieši inštanciu so zostávajúcimi veľkými vecami, a potom malé veci vráti naspäť. Ako vyriešiť inštanciu s
veľkými veciami?
asymptotická
aproximácia
KAPITOLA 2. OPTIMALIZAČNÉ PROBLÉMY
D
R
A
FT
22
Kapitola 3
3.1
Greedy algoritmy
FT
Techniky návrhu
aproximačných algoritmov
A
*** to do: greedy matroidy, matroid intersection ***
Príkladom použitia greedy algoritmov bol 2-aproximačný algoritmus pre problém
Knapcask. Iným príkladom je algoritmus na hľadanie maximálnej nezávislej množiny v grafe, t.j. množiny vrcholov, z ktorých žiadne dva nie sú spojené hranou:
Definícia 3.1 Majme daný graf G = (V, E) cieľom je nájsť maximálnu množinu
vrcholov V 0 ⊆ V tak, aby pre každú hranu e = (u, v) ∈ E platí u 6∈ V 0 alebo v 6∈ V 0 .
R
Intuícia nám vraví, že zlé vrcholy sú také, ktoré majú veľký stupeň, pretože
blokujú veľa iných vrcholov. Uvažujme teda nasledujúci greedy algoritmus (Algoritmus 7), ktorý sme už implicitne použili v Algoritme 5 na vrcholové farbenie:
MaxIndependent
Set
D
Algoritmus 7 Greedy algoritmus pre problém Max-Independent-Set
1: vstup: graf G = (V, E)
2: výstup: nezávislá množina V 0
3: V 0 := ∅, U := V
4: while U 6= ∅ do
5:
nech x je vrchol s minimálnym stupňon z podgrafu indukovaného U
6:
V 0 := V 0 ∪ {x}
7:
U := U \ {x}
8:
U := U \ N eigh(x)
9: end while
Žiaľ, tento algoritmus nie je dobrý aproximačný algoritmus, ako ukazuje obrázok 3.1.
Majme graf G, ktorý pozostáva z úplného grafu Kn , nezávislej množiny In a
vrchola v tak, že každý vrchol z Kn ∪ {v} je spojený hranou s každým vrcholom z
In . Pretože vrchol v má minimálny stupeň, Algoritmus 7 ho vyberie do nezávislej
množiny. Lenže potom ľahko vidno, že nemôže pridať žiaden vrchol z In a iba jeden
vrchol z Kn , t.j. vráti dvojprvkovú nezávislú množinu. Zjavne ale In tvorí n-prvkovú
nezávislú množinu, preto Algoritmus 7 nemá ohraničený aproximačný pomer.
Napriek tomuto nepriazdnivému výsledku Algoritmus 7 celkom nezahodíme.
Ukáže sa totiž, že funguje dobre na grafoch, ktoré sú riedke, t.j. majú málo hrán.
Definícia 3.2 Majme graf G = (V, E). Potom číslo δ = |E|/|V | sa nazýva hustota
grafu G.
23
hustota grafu
24 KAPITOLA 3. TECHNIKY NÁVRHU APROXIMAČNÝCH ALGORITMOV
In
Kn
FT
v
Obr. 3.1: Greedy algoritmus pre problém Max-Independent-Set
Ukážeme teraz, že Algoritmus 7 má ohraničený aproximačný pomer na grafoch
s konštantnou hustotou.
Veta 3.1 Majme daný graf G = (V, E), kde |V | = n, |E| = m a δ = m/n. Nech
mG je veľkosť nezávislej množiny nájdenej Algoritmom 7. Potom
mG ≥
n
2δ + 1
A
Dôkaz: Uvažujme iterácie while cyklu na riadku 4. V každej iterácii sa pridá
jjeden vrchol do nezávislej množiny, preto počet iterácií je mG . V i-tej iterácii sa
vyberie vrchol xi so stupňom di a z grafu sa odstráni xi aj jeho di susedov. Nakoniec
sa odstránia všetky vrcholy, takže
mG
X
(di + 1) = n
(3.1)
i=1
R
Keďže xi mal minimálny stupeň, v i-tej iterácii sa odstráni aspoň 12 di (di + 1) hrán1 .
Pretože sme nemohli odstrániť viac hrán, ako ich v grafe pôvodne bolo, dostávame
mG
X
di (di + 1) ≤ 2m = 2nδ
(3.2)
i=1
D
Sčítaním (3.1) a (3.1) dostaneme
mG
X
(di + 1)2 ≤ n(2δ + 1)
i=1
Ľavú stranu prenásobíme rafinovane zapísanou jednotkou a použijeme CauchySchwarzovu nerovnosť
!2
2 X
mG mG
mG
X
X
1
1
n2
2
·
n(2δ + 1) ≥
(di + 1) ≥
di + 1
=
√
mG
mG i=1
mG
i=1
k=1
kde posledná rovnosť vyplýva z (3.1).
Dôsledok 3.2 Pre grafy s konštantnou hustotou (napr. planárne grafy, grafy s
ohraničeným stupňom, a pod.) je problém nájdenia maximálnej nezávislej množiny
v APX.
1 odstránili sme d + 1 vrcholov, každý stupňa aspoň d , čiže d (d + 1) polhrán; každá hrana
i
i
i i
má najviac 2 polhrany
3.2. LINEÁRNE PROGRAMOVANIE
25
Dôsledok 3.3 Každý graf s n vrcholmi a m hranami obsahuje nezávislú množinu
n2
veľkosi aspoň 2m+n
Rôzne verzie plánovacích (scheduling) a umiestňovacích (packing) problémov
sú taktiež často riešené greedy algoritmami. Najprv prezentujeme problém plánovania úloh na nezávislých procesoroch, ktorý je zovšeobecnením problému MinPartition:
MinScheduling
FT
Definícia 3.3 Na vstupe je daná konštanta p (počet procesorov) a n úloh, pričom
spracovanie i-tej úlohy na ktoromkoľvek procesore trvá čas ti . Cieľom je nájsť priradenie úloh procesorom, nt.j. funkciu f : {1, . . . , n}
o 7→ {1, . . . , p}, tak aby celkový
P
čas spracovania, t.j. max
f (i)=k ti | k = 1, . . . , p , bol minimálny.
Jednoduchý greedy algoritmus, riešiaci problém Min-Scheduling najprv utriedi
úlohy podľa dĺžky. Potom ich sekvenčne spracováva, pričom každú úlohu priradí
procesoru, ktorý je momentálne najmenej zaťažený.
Veta 3.4 Greedy
algoritmus
pre problém Min-Scheduling má aproximačný po
1
mer najviac 34 − 3p
.
A
Dôkaz:
Označme mG cenu greedy riešenia a m∗ optimálnu cenu. Nech W =
Pn
i=1 ti je celkový čas všetkých
P úloh. Bez ujmy na všeobecnosti nech t1 ≥ t2 ≥
· · · ≥ tn , a nech maximum f (i)=k ti sa dosahuje na prvom procesore, t.j. mG =
P
f (i)=1 ti . Nech th je posledná úloha, ktorú algoritmus proradil procesoru 1. Rozlíšime dva prípady:
∗
R
prípad 1: th ≤ m3
V čase, keď algoritmus priradil h-tu úlohu prvému procesoru, tento už mal priradené
úlohy s celkovým časom m − th . Navyše, všetky ostatné procesory mali priradené
úlohy s väčším celkovým časom, takže W ≥ p(m − th ) + th , odkiaľ dostaneme
m≤
w + th (p − 1)
p
D
Pretože th ≤ m∗ /3 a m∗ ≥ W/p dosadením dostaneme
4
1
m≤
−
m∗
3 3p
∗
prípad 2: th > m3
Ukážeme, že v tomto prípade algoritmus vráti optimálne riešenie.
*** to do: po položení každý max. 2 veci, v opt tiež ***
3.2
Lineárne programovanie
Priblížime si dva spôsoby využitia LP pri návrhu aproximačných algoritmov. Budeme ich ilustrovať na probléme minimálneho vrcholového pokrytia:
Definícia 3.4 Majme daný graf G = (V, E) s n vrcholmi a m hranami, pričom i-ty
vrchol má váhu ωi ∈ R+ . Cieľom je nájsť množinu vrcholov V 0 ⊆ V s najmenšou
celkovou váhou, ktorá pokrýva všekty hrany, t.j.
∀(u, v) ∈ E : u ∈ V 0 ∨ v ∈ V 0
minimálne
vrcholové
pokrytie
26 KAPITOLA 3. TECHNIKY NÁVRHU APROXIMAČNÝCH ALGORITMOV
Ideme teraz formulovať problém vrcholového pokrytia v jazyku lineárneho programovania. Pre každý vrchol vi budeme mať premennú xi ∈ {0, 1}, pričom xi = 1
práve vtedy,P
ak je vrchol vi ∈ V 0 . Cieľom je minimalizovať váhu vybraných vrcholov,
n
t.j. funkciu i=1 ωi xi . Zároveň ale vyžadujeme, aby každá hrana bola pokrytá, t.j.
∀(vi , vj ) ∈ E : xi = 1 ∨ xj = 1
čo ekvivalentne zapíšeme
∀(vi , vj ) ∈ E : xi + xj ≥ 1
FT
Nech teraz A je matica n × m taká, že aij = 1 práve vtedy, ak vrchol vi je
koncovým vrcholom hrany ej , a vektor ω je vektor váh vrcholov. Problém nájdenia
najmenšieho vrcholového pokrytia teda môžeme zapísať ako problém celočíselného
lineárneho programovania:
min ω T x | AT x ≥ 1, x ∈ {0, 1}n
Prvým prístupom je najprv vyriešiť v polynomiálnom čase relaxovaný problém
min ω T x | AT x ≥ 1, x ≥ 0
A
Výsledkom budú hodnoty xi ≥ 0 pre každý vrchol vi . Výslednú pokrývaciu množinu musíme skonštruovať vhodným zaokrúhľovaním; v našom prípade vyberieme
tie vrcholy vi , pre ktoré je xi ≥ 1/2.2
Algoritmus 8 Minimálne vrcholové pokrytie pomocou relaxácie ILP
1: m0 :=min ω T x | AT x ≥ 1, x ≥ 0 , x je príslušné optimálne riešenie
2: V 0 :={vi | xi ≥ 1/2}
R
Veta 3.5 Nech V 0 je množina, ktorú vráti algoritmus 8. Potom V 0 je vrcholové
pokrytie. Navyše, nech m∗ je veľkosť minimálneho vrcholového pokrytia, a nech
|V 0 | = m. Potom m ≤ 2m∗ .
D
Dôkaz: Nech x vektor optimálneho riešenia relaxovaného problému. Najprv ukážeme, že V 0 je vrcholové pokrytie: predpokladajme sporom, že existuje hrana (vi , vj ) ∈
E, ktorá je nepokrytá, t.j. xi < 1/2 aj xj < 1/2. Potom ale xi + xj < 1, čo je spor s
ohraničeniami LP, takže x nemohlo byť prípustné (a teda ani optimálne) riešenie.
Teraz odhadneme maximálnu chybu Algoritmu 8. Platí
m∗ ≥ m0 =
n
X
i=1
ωi xi ≥
n
X
i=1
xi ≥1/2
ωi xi ≥
n
1
1 X
ωi = m
2 i=1
2
xi ≥1/2
Prvá nerovnosť vyplýva z toho, že optimálne celočíselné riešenie je prípustné riešenie
relaxovaného problému.
Nevýhodou tohoto prístupu je, že treba presne vyriešiť relaxovaný problém, čo
je výpočtovo pomerne náročné. Druhý, rafinovanejší, prístup spočíva vo využití duality LP bez nutnosti explicitne riešiť LP. Táto technika sa zvykne označovať ako
primárno-duálne algoritmy. Primárno-duálne algoritmy zároveň s riešením primárnej úlohy konštruujú aj riešenie duálnej úlohy. V prípade vrcholového pokrytia bude
2 Čitateľ
sa ľahko presvedčí, že v optimálnom riešení sú xi ≤ 1. Intuícia je, že po vyriešení
relaxovanej úlohy je každý vrchol vybratý s ”pravdepodobnosťou” xi . Do výsledného riešenia
vyberieme tie, ktoré sú vybraté s viac ako polovičnou ”pravdepodobnosťou”.
3.2. LINEÁRNE PROGRAMOVANIE
27
postup nasledovný: začneme s prípustným, ale nie nutne optimálnym, riešením duálnej úlohy y, ktorému zodpovedá nie nutne prípustné, ale o to optimálnejšie, riešenie
primárnej úlohy x. V jednej iterácii algoritmu upravíme x a y tak, že y sa stane
”optimálnejšie” a x sa stane ”prípustnejšie”.
Konrétny algoritmus bude vyzerať takto. Uvažujme dvojicu primárnej a duálnej
úlohy:
P : min ω T x | AT x ≥ 1, x ≥ 0
D : max 1T y | Ay ≤ ω, y ≥ 0
A
FT
Kým primárnu úlohu interpretujeme tak, že vyberáme vrcholy (premenné xi )
tak, aby každá hrana bola pokrytá, duálnu úlohu si môžme predstaviť tak, že zaťažujeme hrany (premenné yi ). Ohraničenia duálnej úlohy nám hovoria, že zaťaženie
každého vrchola, definované ako suma zaťažení incidentných hrán, musí byť najviac ωi . Algoritmus 9 konštruuje súbežne primárne aj duálne riešenie. Vektor y
obsahuje ohodnotenia hrán a vždy spĺňa duálne ohraničenia, t.j. Ay ≤ ω. V 0 je
množina vrcholov v, pre ktoré [Ay]v = ωv . Ak V 0 ešte netvorí vrcholové pokrytie,
vyberieme ľubovoľnú hranu (u, w), ktorá nie je pokrytá. Nech
Ppríslušná duálna premenná je yi . Keďže v duálnej úlohe chceme maximalizovať
yi , skúsme postupne
plynule zväčšovať yi . Toto môžme iba dovtedy, kým sú splnené ohraničenia Ay ≤ ω.
Zväčšovaním yi sa zväčšujú dve pozície vektora Ay, ktoré prislúchajú vrcholom u
a w (viď. obr 3.2), takže so zväčšovaním musíme prestať, akonáhle jedna z týchto
hodnôt dosiahne rovnosť. V tom prípade pridáme príslušný vrchol do pokrytia a
pokračujeme ďalšou iteráciou.
y
i
1
w
1
R
u
×
=
yi
A
D
Obr. 3.2: jedna iterácia primárno-duálneho algoritmu
Algoritmus 9 Minimálne vrcholové pokrytie pomocou primárno-duálneho prístupu
1: y := 0,V 0 = ∅
2: while V 0 nie je vrcholové pokrytie do
3:
vyber nepokrytú hranu (u, w) ∈ E; nech yi je príslušná duálna premenná
4:
zvýš yi tak, aby ostali splnené duálne ohraničenia
5:
if [Ay]u = ωu then
6:
V 0 := V 0 ∪ {u}
7:
else
8:
V 0 := V 0 ∪ {w}
9:
end if
10: end while
Veta 3.6 Nech V 0 je množina, ktorú vráti algoritmus 8. Potom V 0 je vrcholové
pokrytie. Navyše, nech m∗ je veľkosť minimálneho vrcholového pokrytia, a nech
|V 0 | = m. Potom m ≤ 2m∗ .
28 KAPITOLA 3. TECHNIKY NÁVRHU APROXIMAČNÝCH ALGORITMOV
Dôkaz: Kým V 0 nie je pokrytie, algoritmus neskončí. Keďže sa v každej iterácii
pridá vrchol, po najviac n iteráciách algoritmus skončí. Veľkosť V 0 sa dá odhadnúť
nasledovne. Pre každý vrchol v ∈ V 0 platí [Ay]v = ωv , preto
X
m=
[Ay]v ≤ 1 (Ay) = 2y ≤ 2m∗
v∈V 0
3.2.1
FT
Prvá rovnosť platí preto, lebo do nášho riešenia vyberáme iba vrcholy, pre ktoré
[Ay]v = ωv . V druhej nerovnosti sme namiesto sumy cez vrcholy V 0 uvažovali sumu
cez všetky vrcholy. Nasledujúca rovnosť vyplýva z toho, že 1A = 2, lebo A má v
každom stĺpci práve dve jednotky.
Edmondsov algoritmus
Príkladom použitia primárno-duálnej metódy je známy Edmondsov algoritmus na
nájdenie maximálneho 1-faktora.
Majme daný úplný ohodnotený graf G = (V, E) na n = 2k vrcholoch, pričom
hrana e = (u, v) ∈ E má váhu ω(e). V tejto kapitole uvedieme Edmondsov algoritmus, ktorý nájde v polynomiálnom čase minimálny 1-faktor grafu G. Pripomeňme,
že pojmom 1-faktor (úplné párovanie) označujeme množinu hrán E 0 ⊆ E takú, že
každý vrchol v ∈ V je incidentný práve s jednou hranou z E 0 . Úlohou je nájsť
1-faktor, pre ktorý je súčet váh hrán minimálny, t.j.
X
ω(e)
min
0
A
E
e∈E 0
R
kde minimum je brané cez všetky 1-faktory E 0 . Edmondsov algoritmus je príkladom
primárno-duálneho algoritmu lineárneho programovania. Úlohu nájdenia minimálneho 1-faktora si najprv vyjadríme ako celočíselný lineárny program: pre každú
hranu e zavedieme premennú xe ∈ {0, 1}, ktorá vyjadruje, či je hrana e vybratá do
párovania alebo nie, a vyrobíme množinu lineárnych ohraničení, ktoré zaručia, že
prípustné riešenia budú zodpovedať 1-faktorom:
X
min
xe ω(e)
e∈E
za predpokladov
X
xe
=
1
∀v ∈ V
xe
∈
{0, 1}
∀e ∈ E
D
e=(u,v)
u∈V
Tento lineárny program najprv upravíme v dvoch ohľadoch: najprv pridáme
exponenciálne veľa nových (zdanlivo zbytočných) ohraničení a potom relaxujeme
požiadavku celočíselnosti z xe ∈ {0, 1} na xe ≥ 0. Nové ohraničenia budú vyjadrovať triviálne pozorovanie, že z každej množiny s nepárnym počtom vrcholov musí
vychádzať aspoň 1 hrana 1-faktora. Zavedieme si nasledovné označenie:
hranová hranica
množiny
Definícia 3.5 Majme graf G = (V, E) a množinu vrcholov S ⊆ V . Hranová hranica
množiny S, označovaná δ(S), je množina hrán s jedným koncom v S a druhým mimo
S, t.j.:
δ(S) := {e ∈ E | e = (u, v), u ∈ S, v ∈ V \ S}
Nech S sú aspoň trojprvkové množiny s nepárnym počtom vrcholov, t.j.
S := {S ⊂ V | |S| > 1, |S| nepárne }
Náš lineárny program bude po spomínaných úpravách vyzerať takto:
3.2. LINEÁRNE PROGRAMOVANIE
min
29
X
xe ω(e)
e∈E
za predpokladov
X
xe
=
1
∀v ∈ V
xe
≥ 1
∀S ∈ S
xe
≥ 0
∀e ∈ E
e∈δ({v})
X
e∈δ(S)
max
FT
Ako vysvitne neskôr, existuje celočíselné optimálne riešenie tejto úlohy LP. Jej
vyriešenie preto priamo zodpovedá nájdeniu minimálneho 1-faktora. Pozrime sa
teraz na prislúchajúcu duálnu úlohu. Každému ohraničeniu primárnej úlohy bude
zodpovedať duálna premenná, takže budeme mať premenné ru pre u ∈ V a wS pre
všetky podmnožiny S ∈ S. Každej primárnej premennej (t.j. každej hrane e) potom
zodpovedá duálne ohraničenie, ktoré má jednotkový koeficient pri tých duálnych
premenných (t.j. množinách vrcholov S ∈ S a u ∈ V ), do ktorých hranovej hranice
e patrí. Duálna úloha teda vyzerá takto:
X
wS +
S∈S
ru
u∈V
A
za predpokladov
X
ru + rv +
X
wS
≤
ω(e)
∀e = (u, v) ∈ E
wS
≥
0
∀S ∈ S
S∈S
e∈δ(S)
D
R
Problémom pri riešení tejto dvojice úloh je ich exponenciálna veľkosť – primárna
úloha má exponenciálne veľa ohraničení a duálna úloha má exponenciálne veľa premenných. Našťastie v našom riešení bude väčšina duálnych premenných nulová a
v pamäti si budeme udržiavať iba polynomiálne veľa nenulových duálnych premenných. Takisto nebudeme používať všetky primárne ohraničenia – platnosť väčšiny z
nich bude zrejmá.
Algoritmus si teda bude udržiavať celočíselné primárne riešenie (nie nutne prípustné, ale o to optimálnejšie), a nenulové prvky duálneho prípustného riešenia.
Hlavný cyklus algoritmu potom upraví primárne aj duálne riešenie tak, aby nakoniec bolo primárne riešenie prípustné a platili podmienky komplementarity, ktoré
zaručia jeho optimálnosť. V našom prípade podmienky komplementarity vyzerajú
takto:
S1
S2
∀e = (u, v) ∈ E :
xe > 0 ⇒ ru + rv +
X
wS = ω(e)
S∈S
e∈δ(S)
∀S ∈ S :
wS > 0 ⇒
X
xe = 1
e∈δ(S)
Skúsme teraz dodať duálnej úlohe intuitívnu reprezentáciu. Kým premenné primárnej úlohy zodpovedajú vybratým hranám3 , duálne premenné zodpovedajú bublinám okolo príslušných množín: hodnota wS = z (resp. ru = z) hovorí, že okolo
množiny S (resp. {u}) je veľká (resp. malá) bublina hrúbky z. Podmienka S1 hovorí,
že každá vybratá hrana je plná, t.j. súčet hrúbok všetkých bublín, ktoré pretína sa
3 Keďže máme relaxovaný problém, hrana by mohla byť “čiastočne” vybratá. Ako sme však už
naznačili, primárne riešenie budeme udržiavať celočíselné.
30 KAPITOLA 3. TECHNIKY NÁVRHU APROXIMAČNÝCH ALGORITMOV
A
FT
rovná jej váhe4 . Podmienka S2 hovorí, že každú veľkú bublinu nenulovej hrúbky
opúšťa práve jedna vybratá hrana – most.
Algoritmus si bude udržiavať množinu (nie nutne všetkých) plných hrán L a
množinu vybratých hrán M := {e = (u, v) ∈ E | xe = 1}. Počas celého algoritmu
sa bude zachovávať invariant, že M je párovanie5 a M ⊆ L. Pretože M ⊆ L, bude
zaručené, že S1 ostáva počas celého algoritmu splnená. Navyše, keďže M je párovanie, automaticky dostávame platnosť všetkých (exponenciálne veľa) primárnych
ohraničení týkajúcich sa množín S ∈ S. Pretože podmienka S1 je splnená, algoritmus skončí vtedy, keď bude splnená podmienka S2 a každý vrchol bude spárovaný
v M.
Nenulové prvky duálneho riešenia budeme udržovať vo veľmi špeciálnej forme:
žiadne dve (nenulové) bubliny sa nebudú pretínať a každá nenulová bublina bude
tvoriť tzv. kvet (viď. obr. 3.3).
Obr. 3.3: Kvet.
D
R
Najmenší kvet je tvorený jedným vrcholom – stopkou, uzavretým v malej bubline. Väčší kvet K sa skladá z nepárneho počtu menších kvetov K1 , . . . , K2r+1 ,
ktorých stopky sú pospájané do kružnice hranami z L. Stopka kvetu K1 je zároveň
stopkou kvetu K. Navyše stopky kvetov K2 , . . . , K2r+1 sú popárované hranami z
M . Kvet preto predstavuje v bubline uzavretú “spracovanú” časť grafu – všetky
vrcholy sú spárované a spĺňajú podmienku S2. Stopka kvetu je jediný vrchol, ktorý
treba spárovať mimo kvet. Duálne riešenie, ktoré si bude algoritmus pamätať bude
tvorené množinou kvetov. Navyše vonkajšie kvety6 budú udržiavané v štruktúre,
ktorá sa zvykne označovať ako maďarský les.
maďarský les
Definícia 3.6 Majme daný graf G = (V, E) a v ňom párovanie M ⊂ E. Nech
W ⊆ V je množina vrcholov nepokrytých párovaním M . Graf G0 = (V, F ), F ⊆ E
sa nazýva maďarský les vzhľadom na M , ak G0 je les obsahujúci párovanie M taký,
že každý komponent súvislosti G0 je buď hrana z M alebo strom, ktorý má koreň vo
W a na každej ceste z koreňa do listu sa striedajú hrany z F \ M a M 7 .
Dôležité pozorovanie, ktoré vyplýva z vlastnosti alternovania je, že vrcholy na
nepárnej úrovni8 majú stupeň najviac 2. Vrcholy stromov v našom maďarskom lese
F sú vonkajšie kvety. Hrany stromu sú tvorené hranami z L, ktoré spájajú niektoré
vrcholy z príslušných kvetov. Podľa definície F obsahuje stromy dvoch typov –
dvojice vrcholov spojené hranou z M a tzv. voľné stromy, viď. obr. 3.4. Algoritmus
4 podotýkame,
že plná hrana nemusí byť vybratá
nutne kompletný 1-faktor
6 také, ktoré nie sú súčasťou iného kvetu
7 takúto cestu budeme označovať F − M alternujúca
8 koreň má úroveň 0, jeho synovia úroveň 1, atď.
5 nie
31
FT
3.2. LINEÁRNE PROGRAMOVANIE
Obr. 3.4: Voľný strom z maďarského lesa F .
si bude udržovať maďarský les F . Základnou operáciou na stromoch bude zmena
stromu o danú hodnotu r – k hrúbke každej vonkajšej bubliny na párnej úrovni sa
priráta r a od hrúbky každej vonkajšej bubliny na nepárnej úrovni sa odráta r.
D
R
A
Algoritmus 10 Edmondsov algoritmus na nájdenie minimálneho 1-faktora
1: L = M = ∅
2: F je tvorený n stromami, z ktorých každý pozostáva z vrchola obklopeného
malou bublinou hrúbky 0.
3: while M nie je 1-faktor do
4:
operácia zmena(r) na všetkých voľných stromoch, pričom r je najmenšie
také číslo, že nastane jeden z nasledujúcich prípadov:
5:
A: niektorá vonkajšia bublina dosiahla hrúbku 0: Keďže zmiznutá
bublina bola na nepárnej úrovni, mala stupeň najviac 2. Vnútorné kvety
zo zmiznutej bubliny tvoriace alternujúcu cestu sa zaradia do stromu.
Zvyšné vnútorné kvety budú tvoriť nové dvojvrcholové komponenty F
6:
B: naplnila sa hrana spájajúca dva kvety R, R0 v jednom voľnom
strome T : naplnenú hranu pridáme do L. Obidva kvety boli na párnej
úrovni, preto z vlastnosti alternovania vyplýva, že v T vznikla nepárna
kružnica. Kvety tejto kružnice uzavrieme novým kvetom s hrúbkou 0.
7:
C: naplnila sa hrana spájajúca dva kvety R, R0 vo voľnom strome
T a dvojvrcholovom strome T 0 : naplnenú hranu pridáme do L. Strom
T 0 sa pripojí k T .
8:
D: naplnila sa hrana spájajúca dva kvety R, R0 v dvoch voľných
stromoch T a T 0 : naplnenú hranu pridáme do L. Pretože R aj R0
boli na párnej úrovni, rekurzívne nájdeme zväčšujúcu alternujúcu cestu
p medzi koreňmi T a T 0 . Zväčšíme párovanie M pozdĺž p. Rekurzívne
rozoberieme voľné stromy T a T 0 a do F pridáme vzniknuté dvojvrcholové
komponenty.
9: end while
Veta 3.7 Algoritmus 10 vykoná najviac O(n2 ) iterácií a skončí s najmenším 1faktorom M .
Dôkaz: Keď algoritmus skončí, M je 1-faktor. Z predchádzajúcich úvah vyplýva,
že pri skončení je M a F primárne a duálne riešenie a platia podmienky komplementarity.
Počet iterácií odhadneme nasledovne: M monotónne rastie, preto prípad D nastane max. O(n) krát. Ukážeme, že medzi dvoma výskytmi prípadu D môže nastať
32 KAPITOLA 3. TECHNIKY NÁVRHU APROXIMAČNÝCH ALGORITMOV
iba O(n) výskytov prípadov A,B,C. Prípad C zmenší počet komponentov. Prípady A,B zachovávajú paritu úrovne kvetov – kvety na párnych úrovniach rastú,
na nepárnych sa zmenšujú.
*** to do: poriadnejší dôkaz ***
3.3
Derandomizácia
3.3.1
FT
Jednou z možností, ako dosiahnuť garantovanú kvalitu aproximácie, je využiť existujúci randomizovaný algoritmus a prerobiť ho na deterministický. Ukážeme si všeobecnú techniku známu ako metóda podmienených pravdepodobností a aplikujeme
ju na istú verziu problému splniteľnosti.
Metóda podmienených pravdepodobností
A
Predpokladajme, že máme maximalizačný9 problém P a randomizovaný algoritmus
A, ktorý ho rieši. Nech výstup A na vstupe x je nádodná premenná Zx . Naším cieľom je navrhnúť deterministický algoritmus, ktorý pre vstup x nájde riešenie s hodnotou aspoň E[Zx ]10 . Algoritmus A počíta tak, že využíva postupnosť náhodných
bitov y1 , y2 , . . . , ym , pričom yi = 1 s pravdepodobnosťou pi . Budeme ho postupne
upravovať tak, že niektoré náhodné bity zafixujeme: ak za náhodné bity y1 , . . . , yk
dosadíme konštanty d1 , . . . , dk , dostaneme randomizovaný algoritmus, ktorý používa m − k náhodných bitov; ak k = m, dostávame deterministický algoritmus.
Označme E[Zx |d1 , . . . , dk ] očakávaný výstup algoritmu A, ak je prvých k bitov zafixovaných na konštanty d1 , . . . , dk a zvyšné bity sú náhodné. Predpokladajme, že
vieme deterministicky v polynomiálnom čase zrátať hodnoty E[Zx |d1 , . . . , dk ]. Derandomizačná procedúra bude postupne fixovať náhodné bity, využívajúc pri tom
fakt, že
R
E[Zx |d1 , . . . , dk ] = pk+1 E[Zx |d1 , . . . , dk , 1] + (1 − pk+1 )E[Zx |d1 , . . . , dk , 0]
Preto ak E[Zx |d1 , . . . , dk , 1] > E[Zx |d1 , . . . , dk , 0], zvolíme dk+1 = 1 a dostaneme
E[Zx |d1 , . . . , dk ] ≤ E[Zx |d1 , . . . , dk , dk+1 ]
D
a obdobne pre opačný prípad. Nakoniec získame deterministický algoritmus, ktorého
riešenie je aspoň E[Zx ].
3.3.2
Derandomizácia aplikovaná na problém MAX-E3-SAT
Problém MAX-E3-SAT je variantou problému splniteľnosti:
MAX-E3-SAT
Definícia 3.7 Majme danú formulu v konjunktívnom normálnom tvare (t.j. ako
konjunkciu m klauzúl nad logickými premennými x1 , . . . , xn ), pričom každá klauzula
má práve tri rôzne literály. Cieľom je nájsť také pravdivostné priradenie logických
hodnôt premenným, aby čo najviac klauzúl bolo splnených.
Problém MAX-E3-SAT je NP-ťažký.
Veta 3.8 Pre problém MAX-E3-SAT existuje 8/7-aproximačný algoritmus.
9 postup
pre minimalizačné problémy je analogický
P
riešenie určite existuje: keďže A vracia iba prípustné riešenia a E[Zx ] = i i·P [Zx = i],
musí existovať riešenie s hodnotou i, ktorá je aspoň taká ako vážený priemer.
10 Takéto
3.3. DERANDOMIZÁCIA
33
Dôkaz: Uvažujme jednoduchý
xi ohodnotí nezávisle náhodne
čet splnených klauzúl? Nech X
klauzúl, a nech Xi je náhodná
Zrejme
randomizovaný algoritmus, ktorý každú premennú
s pravdepodobnosťou 1/2. Aký je očakávaný poje náhodná premenná udávajúca počet splnených
premenná udávajúca, či je i-ta klauzula splnená.
X=
m
X
Xi
i=1
a teda
E[X] =
m
X
E[Xi ]
FT
i=1
A
Na to, aby bola i-ta klauzula splnená, stačí, aby bol splnený aspoň jeden jej literál.
Pretože klauzula má tri literály a každý je splnený nezávisle s pravdepodobnosťou
1/2, je E[Xi ] = 7/8, takže očakávaný počet splnených klauzúl je E[X] = 7m/8.
Teraz vieme, že pri náhodonom ohodnotení premenných je očakávaný počet
splnených klauzúl 7m/8. To ale znamená, že určite existuje také ohodnotenie premenných, ktoré splní aspoň 7/8 všetkých klauzúl. Ak by sme takéto ohodnotenie
vedeli nájsť, dostaneme zjavne 8/7-aproximačný algoritmus.
Na deterministické nájdenie vhodného ohodnotenia použijeme techinku podmienených pravdepodobností. Pre čiastočné ohodnotenie x1 = v1 , . . . , xi = vi označme
E[X|x1 = v1 , . . . , xi = vi ] očakávaný počet splnených klauzúl, ak hodnoty prvých
i premenných sú fixované a zvyšné premenné sú ohodnotené nezávisle náhodne.
Ohodnotenie budeme konštruovať induktívne začínajúc z prázdneho ohodnotenia,
pre ktoré vieme, že E[X] = 7m/8. Predpokladajme teraz, že máme skonštruované
ohodnotenie x1 = v1 , . . . , xi = vi . Chceme nájsť priradenie xi+1 = vi+1 tak, aby
E[X|x1 = v1 , . . . , xi+1 = vi+1 ] ≥ E[X|x1 = v1 , . . . , xi = vi ]. Pretože nezafixované
premenné sú ohodnotené nezávislo náhodne, platí
1
1
E[X|x1 = v1 , . . . , xi+1 = 0]+ E[X|x1 = v1 , . . . , xi+1 = 1]
2
2
R
E[X|x1 = v1 , . . . , xi = vi ] =
Ak
E[X|x1 = v1 , . . . , xi+1 = 0] ≥ E[X|x1 = v1 , . . . , xi+1 = 1]
zvolíme vi+1 = 0, inak vi+1 = 1. Teraz platí
D
E[X|x1 = v1 , . . . , xi = vi ] ≤ E[X|x1 = v1 , . . . , xi+1 = vi+1 ]
Týmto postupom sa dostaneme k ohodnoteniu všetkých premenných, pre ktoré
platí
7
E[X|x1 = v1 , . . . , xn = vn ] ≥ m
8
takže máme deterministický 8/7-aproximačný algoritmus.
Posledná vec, ktorú nám ostáva ukázať, je ako deterministicky vyhodnotiť výrazy
tvaru
E[X|x1 = v1 , . . . , xi = vi ]
Na to nám ale stačí, podobne ako v našich úvahách na začiatku, vypočítať pre j-tu
klauzulu jej očakávaný príspevok
E[Xj |x1 = v1 , . . . , xi = vi ]
*** to do: použitie expanderov ***
34 KAPITOLA 3. TECHNIKY NÁVRHU APROXIMAČNÝCH ALGORITMOV
3.4
Vonkajškoplanárna dekompozícia
Pri navrhovaní aproximačných algoritmov pre planárne grafy sa často využíva tzv.
vonkajškoplanárna dekompozícia.
Definícia 3.8 Planárny graf G = (V, E) nazveme vonkajškoplanárny, ak existuje
také jeho planárne vnorenie do roviny, že všetky vrcholy ležia na hranici vonkajšej
oblasti.
FT
vonkajškoplanárny
graf
Obr. 3.5: Vonkajškoplanárny graf
D
R
A
Hlavná myšlienka techniky vonkajškoplanárnej dekompozície je založená na tom,
že mnohé problémy, ktoré sú pre planárne grafy ťažké, sú efektívne riešiteľné pre
vonkajškoplanárne grafy. Keď si teraz zoberieme ľubovoľný planárny graf a jeho
vnorenie do roviny, môžeme ho rozložiť na vonkajškoplanárne úrovne: vrcholy na
harnici vonkajšej oblasti budú mať úroveň 1. Keď ich odstránime (aj s incidentnými
hranami), dostaneme opäť planárny graf. Vrcholy na hranici vonkajšej oblasti nového grafu budú mať úroveň 2 a celý postup opakujeme. Planárny graf nazveme
k-vonkajškoplanárny, ak má k úrovní vonkajškoplanárnej dekompozície.
Obr. 3.6: 3-vonkajškoplanárna dekompozícia planárneho grafu. Vrcholy úrovne 1 sú
červené, vrcholy úrovne 2 zelené a vrcholy úrovne 3 modré.
Pri k-vonkajškoplanárnej dekompozícii vrcholy jednej úrovne indukujú (nie nutne
súvislý) vonkajškoplanárny graf; zvyšné hrany spájajú iba vrcholy dvoch susených
úrovní. Toto pozorovanie sa často dá využiť na to, aby sme izolovali ”exponenciálnosť”: z algoritmu pracujúceho v čase O(p(n)) pre nejaký polynóm p(n) na
vonkajškoplanárnych grafoch získame algoritmus pracujúci v čase O(f (k)q(n)) na
planárnych grafoch, pričom q(n) je polynóm a f (k) je (možno exponenciálna) funkcia, ktorá nezávisí od n.
Ďalší postup je taký, že z grafu vyhodíme niektoré úrovne tak, aby sa nám
rozpadol na k-vonkajškoplanárne grafy pre malé k, na ktorých vieme nájsť optimálne
riešenie, a potom ukážeme, že toto riešenie je dosť dobré aj pre celý graf.
3.4. VONKAJŠKOPLANÁRNA DEKOMPOZÍCIA
35
Ako príklad si zoberme problém nájdenia maximálnej nezávislej množiny v planárnych grafoch, prevzatý z [?]
Definícia 3.9 Majme graf G = (V, E). Možinu vrcholov V 0 ⊆ V nazveme nezávislá,
ak žiadne dva vrcholy z V 0 nie sú spojené hranou, t.j. ∀u, v ∈ V 0 : (u, v) 6∈ E.
nezávislá
množina
Nájsť maximálnu nezávislú množinu v planárnom grafe je NP-ťažký problém,
avšak pre vonkajškoplanárne grafy existuje lineárny algoritmus:
FT
Veta 3.9 Existuje algoritmus A, ktorý pre daný vonkajškoplanárny graf G = (V, E)
nájde maximálnu nezávislú množinu v čase O(n).
Predpokladajme, že máme daný súvislý vonkajškoplanárny graf a jeho vnorenie
s vrcholmi zoradenými v kladnom smere. Ak graf obsahuje most11 (u, v), nahradíme
ho dvomi hranami medzi u a v – zbavíme sa tak špeciálneho prípadu a ďalej môžme
uvažovať grafy bez mostov.
Predpokladajme najprv, že náš graf je dvojsúvislý, t.j. neobsahuje artikulácie12 .
Oblasti grafu G majú špeciálnu štruktúru, ktorú využijeme pri návrhu algoritmu.
Najprv si zadefinujeme graf oblastí13
Definícia 3.10 Majme daný vonkajškoplanárny graf G = (V, E) bez mostov a artikulácií. Graf G = (V 0 , E 0 ) zostrojíme nasledovne:
A
1. pre každú hranu e ∈ E ležiacu na vonkajšej oblasti, V 0 obsahuje vrchol ve
2. pre každú vnútornú oblasť f , V 0 obsahuje vrchol vf .
3. vrchol vf je spojený hranou z E 0 s vrcholmi ve , ak hrana e ∈ E leží na hranici
oblasti f
4. vrchol vf je spojený hranou z E 0 s vrcholmi vf 0 , ak oblasti f a f 0 majú spoločnú
hranu
R
2
4
3
1
5
D
6
9
7
8
Obr. 3.7: Vonkajškoplanárny graf G a jeho graf oblastí
Ľahko vidno, že graf oblastí je strom, ktorý možno skonštruovať v lineárnom
čase prechádzaním po hranici vonkajšej oblasti. Každeému vrcholu stromu môžeme
zároveň priradiť dvojicu vrcholov, reprezentujúcu úsek na vonkajšej oblasti: listu,
ktorý zodpovedá vonkajšej hrane (vi , vi+1 ) priradíme dvojicu (i, i + 1). Vnútornému
vrcholu priradíme dvojicu (u, v), kde u je minimum spomedzi vrcholov vyskytujúcich sa v dvojiciach priradených jeho synom a v je maximum.
*** to do: pridať artikulácie ***
11 Most
je hrana grafu, ktorej odobratie zvýši počet komponentov súvislosti
je vrchol grafu, ktorého odobratie zvýši počet komponentov súvislosti
13 Čitateľovi znalému teórie grafov isto neuniklo, že graf oblastí je jemne modifikovaný duálny
graf: nech v0 je vrchol duálneho grafu G∗ zodpovedajúci vonkajšej oblasti. Graf oblastí dostaneme
z G∗ subdivíziou každej hrany incidentnej s v0 a následným odstránením v0 .
12 Artikulácia
graf oblastí
36 KAPITOLA 3. TECHNIKY NÁVRHU APROXIMAČNÝCH ALGORITMOV
(1,1)
(1,3)
(1,2)
(2,3)
(3,7)
(3,4)
(4,6)
(4,5)
(7,9)
(6,7)
(7,8)
(9,1)
(8,9)
(5,6)
FT
Obr. 3.8: Strom prislúchajúci grafu z Obr.3.7
Algoritmus bude postupovať od listov stromu smerom ku koreňu, pričom v každom vrchole označenom (u, v) si bude pamätať veľkosť najväčšej nezávislej množiny na úseku u–v pre štyri prípady podľa toho ktoré z krajných bodov sú vybraté.
Zjavne vo vnútornom vrchole stačí v každom zo štyroch prípadov greedy metódou
prechádzať deti zľava doprava.
*** to do: podrobnejšie rozpísať ***
Zovšeobecnením tohoto prístupu dostaneme algoritmus pre k-vonkajškoplanárne
grafy
Veta 3.10 Existuje algoritmus A, ktorý pre daný k-vonkajškoplanárny graf G =
(V, E) nájde maximálnu nezávislú množinu v čase O(8k n).
R
A
*** to do: dôkaz? ***
Teraz ukážeme, ako využiť predchádzajúci algoritmus na vyrobenie PTAS pre
nájdenie maximálnej nezávislej množiny v planárnych grafoch. Majme daný planárny graf G = (V, E). Nech jeho vonkajškoplanárna dekompozícia má s úrovní.
Zvoľme si nejakú konštantu k. Ak vyhodíme každú k+1-vú úroveň, graf sa rozpadne
na komponenty, z ktorých každý je k-vonkajškoplanárny. Existuje k + 1 posunutí,
ktoré úrovne modulo k + 1 vyhodiť. Vyskúšame všekty možnosti a vyberieme tú,
ktorá dáva najlepší výsledok (viď. Algoritmus 11).
D
Algoritmus 11 PTAS pre maximálnu nezávislú množinu v planárnych grafoch
l
m
1
1: k := r−1
2: nájdi planárne vnorenie; nech Vi sú vrcholy na úrovni i
3: for i = 0 to k do
S
4:
Vi := j≡i(mod k+1) Vj
5:
nech Gi je graf indukovaný vrcholmi V − Vi
6:
Ii := maximálna nezávislá množina Gi
7: end for
8: return max Ii
Veta 3.11 Algoritmus 11 je PTAS pre problém nájdenia maximálnej nezávislej
množiny v planárnych grafoch.
Dôkaz:
Chceme dosiahnuť pomer aproximácie r, t.j. ak algoritmus vráti množinu I, tak
|I ∗ |/|I| ≤ r, kde I ∗ je maximálna nezávislá množina. Uvažujme všsetky grafy Gi .
Zjavne podľa Dirichletovho prinípu existuje s, že najviac k + 1-tina vrcholov z I ∗
leží v Vs , t.j.
∃s : |Vs ∩ I ∗ | ≤
|I ∗ |
k+1
3.4. VONKAJŠKOPLANÁRNA DEKOMPOZÍCIA
37
Z toho vyplýva, že Is má v Gs aspoň k/(k + 1)|I ∗ | vrcholov, čiže aproximačný
pomer je (k + 1)/k = r. Keďže pre dané r je k konštanta, nájdenie maximálnej
nezávislej množiny Ii je linárne, a algoritmus je PTAS.
D
R
A
FT
*** to do: spomenúť ďalšie problémy s rovnakou technikou ***
D
R
A
FT
38 KAPITOLA 3. TECHNIKY NÁVRHU APROXIMAČNÝCH ALGORITMOV
Kapitola 4
FT
Negatívne výsledky o
aproximácii
*** to do: polynomiálne ohraničené nemajú FPTAS ***
4.1
Pravdepodobnostne overiteľné dôkazy (PCP)
D
R
A
V tejto časti sformulujeme tzv. PCPvetu, ktorá prináša alternatívnu charakterizáciu
triedy NP. Ukáže sa, že táto charakterizácia umožňuje dokazovať silné tvrdenia
o neaproximovateľnosti optimalizačných problémov za predpokladu P 6= NP, čím
dokumentuje zaujímavú súvislosť medzi zložitosťou a aproximovateľnosťou.
PCP veta sa týka formálnych zariadení označovaných ako verifikátory. Prv než
ich zadefinujeme, pripomeňme, že NP je trieda jazykov rozpoznávaných nejakým
nedeterministickým Turingovým strojom pracujúcim v polynomiálnom čase, t.j. ak
dané slovo patrí do jazyka, existuje polynomiálny akceptujúci výpočet, ak nepatrí,
žiaden výpočet neakceptuje. Sériu nedeterministických rozodnutí akceptujúceho výpočtu môžeme teda chápať ako dôkaz toho, že dané slovo patrí do jazyka. Na triedu
NP sa preto môžme alternatívne pozrieť takto: nech verifikátor je deterministický
Turingov stroj pracujúci v polynomiálnom čase, ktorý má navyše špeciálnu, tzv.
dôkazovú pásku. Verifikátor rozpoznáva jazyk L, ak pre každé slovo x ∈ L existuje
dôkaz π taký, že verifikátor na vstupe x s dôkazom π akceptuje, a pre každé slovo
x 6∈ L neexistuje žiaden dôkaz, s ktorým by verifikátor akceptoval1 . Modifikujme
ďalej verifikátor tak, že mu obmedzíme prístup k dôkazu: namiesto priameho čítania
dôkazovej pásky môže vygenerovať q otázok: na dôkazovú pásku zapíše q pozícií; v
jednom kroku potom dostane odpovede – bity v dôkaze na príslušných pozíciách.
Ako kompenzáciu za toto oslabenie verifikátoru pridáme možnosť pracovať s náhodnými číslami tak, aby jeho rozpoznávacia sila ostala zachovaná (t.j.aby rozpoznával
triedu NP).
Definícia 4.1 (r, q)-verifikátor V je deterministický TS s dvoma špeciálnymi páskami: náhodnou a dôkazovou. V pracuje na vstupnom slove x tak, že na začiatku je
na vstupnej páske napísané x a na náhodnej páske je napísaný binárny reťazec dĺžky
r. V v polynomiálnom čase zapíše na dôkazovú pásku q binárnych čísel a1 , . . . , aq
oddelených znakom ”#” a prejde do špeciálneho pýtacieho stavu. V nasledujúcom
kroku V prejde do odpoveďového stavu, na dôkazovej páske je napísaný binárny
reťazec dĺžky q a na náhodnej páske sú samé nuly2 . V potom v polynomiálnom čase
dá odpoveď.
1 pomôže
predstava dôkazu ako postupnosti rozhodnutí nedeterministického TS
verifikátor je neadaptívny – položené otázky nemôžu závisieť od predchádzajúcich odpovedí,
a navyše po obdržaní odpovede stratí prístup k náhodným bitom.
2 t.j.
39
(r, q)-verifikátor
40
KAPITOLA 4. NEGATÍVNE VÝSLEDKY O APROXIMÁCII
Nech ρ je binárny reťazec dĺžky r a π je binárny reťazec. Povieme, že V počíta
na vstupe x s náhodným reťazcom ρ a dôkazom π, ak na začiatku je na vstupnej
páske napísané x, na náhodnej páske ρ a v odpoveďovom stave je na dôkazovej páske
reťazec πa1 , . . . , πaq , kde πi je i-ty bit reťazca π. Výstup V v tomto prípade označíme
V(x, ρ, π).
Jazyk L je akceptovaný verifikátorom V, ak pre každé slovo x platí:
x ∈ L ⇒ ∃π : P [V(x, ρ, π) = Yes] = 1
x 6∈ L ⇒ ∀π : P [V(x, ρ, π) = Yes] ≤ 12
FT
pričom pravdepodobnosť sa berie cez všetky náhodné reťazce ρ.
Neformálne povedané, verifikátor akceptuje jazyk L, ak pre slová z L existuje
dôkaz, ktorý ho určite presvedčí, a pre slová nepatriace do L ho žiaden dôkaz nepresvedčí s veľkou pravdepodobnosťou.
Označme PCP[r(n), q(n)] triedu jazykov rozpoznávaných (r(n), q(n))-verifikátorom.
Ľahko vidno, že NP = PCP[0, poly], t.j. verifikátor bez náhodných bitov, ktorý môže
čítať polynomiálne veľa bitov dôkazu je ekvivalentný nedeterministickému TS.3
Prekvapivé a silno netriviálne tvrdenie je:
PCPveta
Veta 4.1
NP = PCP [O(log n), O(1)]
A
Poznamenajme, že jedna inklúzia v predchádzajúcej vete je ľahko nahliadnuteľná: nedeterministický TS vie odsimulovať verifikátor jednoducho tak, že “uhádne”
dôkaz a simuluje spávanie verifikátora pre všetkých 2O(log n) = poly(n) náhodných
reťazcov.
4.2
Použitie PCPvety
R
V tejto časti ukážeme, ako sa dá použiť PCPveta na dôkaz neaproximovateľnosti
nejakého optimalizačného problému.
Veta 4.2 Ak P 6= NP, tak Max-3-Sat 6∈ PTAS.
D
Dôkaz: Budeme postupovať sporom. Predpokladajme, že vieme Max-3-Sat aproximovať s ľubovoľnou presnosťou nejakým PTAS-om A. Potom ukážeme, že P = NP,
t.j. že v polynomiálnom čase vieme (deterministicky) rozhodovať nejaký NP-úplný
jazyk L.
Presnejšie, zoberme si ľubovoľný NP-úplný jazyk L. Popíšeme deterministickú
procedúru, ktorá v polynomiálnom čase pre vstupné slovo x vyrobí formulu ϕx ako
vstup pre Max-3-Sat4 takú, že ak x ∈ L, tak ϕx je splniteľná a ak x 6∈ L, tak v
každom ohodnotení ϕx je aspoň ε-tina klauzúl nesplnená (kde ε je fixná konštanta).
Tvrdíme, že ak sa nám táto konštrukcia podarí, dôkaz je ukončený: Pre daný vstup
x vyrobíme ϕx a nájdeme napr. ε/2-aproximáciu. Nech ϕx má t klauzúl.
Ak x ∈ L,
ϕx je splniteľná, takže A vráti riešenie s hodnotou aspoň t 1 − 2ε . Naopak, ak
x 6∈ L, tak každé riešenie má hodnotu najviac t (1 − ε). Teda na to, aby sme zistli,
či x ∈ L stačí spustiť A na ϕx s presnosťou ε/2 a porovnať výsledok s hodnotou
t 1 − 2ε .
Zostáva nám ukázať, ako zostrojiť ϕx . Podľa PCPvety existuje (r(n), q)-verifikátor
V pre L, kde r(n) ∈ O(log n) a q je konštanta. Ukážeme, ako s pomocou V vyrobiť
deterministicky v polynomiálnom čase ϕx . Pri analýze V nám zjavne stačí brať do
3 Ako
4 t.j.
zaujímavosť uvádzame výsledok z [Babai,Fortnow,Lund,1990], že PCP[poly,poly]= NEXP
v konjunktívnom normálnom tvare, pričom každá klauzula má tri literály
4.2. POUŽITIE PCPVETY
41
FT
úvahy dôkazy dĺžky najviac v = 2r(n) q, keďže toľko je rôznych reťazcov, ktoré V
môže zapísať na dôkazovú pásku. V nami konštruovanej ϕx budú premenné zodpovedať pozíciám v dôkaze; t.j. ϕx bude mať premenné x1 , . . . , xv , pričom každému
dôkazu π zodpovedá prirodzeným spôsobom5 pravdivostné ohodnotenie ϕx a naopak.
Zafixujme si r-bitový reťazec ρ. Verifikátor V s reťazcom ρ na náhodnej páske
pracuje tak, že v polynomiálnom čase vyprodukuje q otázok na pozície p1 , . . . , pq
a podľa príslušných odpovedí vráti výsledok. Nech Aρ je množina takých q-tic odpovedí, pri ktorých V zamietne. Množina Aρ sa dá skonštruovať deterministicky
v polynomiálnom čase6 . Pre každú q-ticu (a1 , . . . , aq ) ∈ Aρ vyrobíme klauzulu
K = l1 ∨ · · · ∨ lq tak, aby K bola splnená, ak príslušné premenné nemajú zaradom hodnoty (a1 , . . . , aq ); t.j. li ≡ xpi ak ai = 0 a li ≡ xpi ak ai = 17 .
Nech A = ∪ρ Aρ je zjednotenie všetkých zamietacích q-tic cez všetky reťazce ρ,
zjavne |A| ≤ 2q+r(n) = poly(n) a nech L je multimnožina8 všetkých prislúchajúcich
klauzúl, pričom zjavne L je skonštruovateľná deterministicky v polynomiálnom čase.
Chceli by sme, aby výsledná formula bola
^
ϕ0x ≡
K
K∈L
A
Táto konštrukcia má však technický problém v tom, že K má q literálov a nie tri.
Riešenie je jednoduché: každú klauzulu K ≡ l1 ∨ · · · ∨ lq ∈ L nahradíme množinou
klauzúl K1 ≡ l1 ∨l2 ∨z1 , K2 ≡ z1 ∨l3 ∨z2 , K3 ≡ z2 ∨l4 ∨z3 , . . . , Kq−2 ≡ zq−3 ∨lq−1 ∨lq ,
kde zi sú nové pomocné premenné tak, že počet klauzúl narastie (q − 2)-násobne.
Teraz môžme definovať
^ q−2
ϕx ≡
∧i=1 Ki
K∈L
keď ϕ0x .
D
R
Zjavne ϕx je splniteľná práve vtedy,
Ak x ∈ L, tak existuje dôkaz π, pre ktorý verifikátor V akceptuje s pravdepodobnosťou 1. Tvrdíme, že potom ohodnotenie získané z π spĺňa ϕ0x : uvažujme sporom,
nech existuje klauzula K = l1 ∨ · · · ∨ lq z ϕ0x , ktorá je nesplnená v ohodnotení9 π,
t.j. v π platí l1 ∧ · · · ∧ lq . Lenže K vznikla na základe nejakej q-tice z Aρ pre nejaký
reťazec ρ takým spôsobom, že ak V dostane na reťazci ρ odpoveď (ako postupnosť
bitov) l1 , . . . , lq tak zamietne. Lenže V nezamietne pri dôkaze π pre žiaden reťazec
ρ. Preto ϕ0x je splniteľná, a teda aj ϕx je splniteľná.
Naopak, ak x 6∈ L tak ukážeme, že v ľubovoľnom ohodnotení ϕx je aspoň ε1
tina klauzúl nesplnená, kde ε = 2q+1
. Nech π je ľubovoľné ohodnotenie ϕx a, opäť
zneužijúc notáciu, aj jeho zúženie na ϕ0x a prislúchajúci dôkaz. Keďže x 6∈ L tak
pre každý dôkaz, a špeciálne aj pre π, verifikátor V zamietne s pravdepodobnosťou
aspoň 1/2, t.j. pre aspoň polovicu (t.j. 2r(n)−1 ) reťazcov ρ existuje v Aρ taká q-tica,
že príslušná klauzula je vo ϕ0x nesplnená. Teda pre fixný dôkaz (resp. ohodnotenie)
π dostávame, že aspoň 2r(n)−1 klauzúl z ϕ0x je nesplnených. Navyše, pre každú
nesplnenú klauzulu K z ϕ0x , musí byť aspoň jedna z klauzúl K1 , . . . , Kq−2 vo ϕx
nesplnená. Preto dostávame, že pre ľubovoľné ohodnotenie ϕx je relatívna početnosť
nesplnených klauzúl aspoň
ε=
5x
i ≡ 1 práve vtedy,
6 Najprv pre dané ρ
2r(n)−1
1
2r(n)−1
≤
≤ q+1
2
(q − 2)2q+r(n)
2q+r(n)
ak je hodnota i-teho bitu dôkazu 1.
simulujeme V až kým neprejde do pýtacieho stavu. Potom postupne simulujeme V pre všetkých 2q = O(1) možností odpovedí a vždy keď zamietne, pridáme príslušnú
q-ticu do Aρ .
7 Napríklad nech sa V pre daný reťazec ρ pýta na pozície 1, 3, 5, 7 dôkazu a ďalej pracuje tak,
že ak dostane odpoveď (0, 0, 1, 1) tak zamietne. Štvorica (0, 0, 1, 1) preto bude v Aρ a príslušná
klauzula bude x1 ∨ x3 ∨ x5 ∨ x7 .
8 klauzuly v L nemusia byť rôzne
9 s trochou zneužitia notácie stotožňujeme dôkaz a prislúchajúce ohodnotenie
42
KAPITOLA 4. NEGATÍVNE VÝSLEDKY O APROXIMÁCII
Keď už poznáme jeden problém, pre ktorý (asi10 ) neexistuje PTAS, môžme dokázať podobné výsledky pre ďalšie problémy pomocou redukcií. Zoberme si napríklad
problém MaxClique, v ktorom je cieľom pre daný graf nájsť najväčšiu kliku (úplný
graf), ktorú obsahuje ako podgraf11 .
Veta 4.3 Ak P 6= NP, tak MaxClique 6∈ PTAS.
x1 x2 ¬x3
x1 x2 ¬x3
¬x1
x1
¬x2
x3
FT
Dôkaz: Ukážeme, že keby sme vedeli dosť presne aproximovať MaxClique, vedeli
by sme dosť presne aproximovať aj Max-3-Sat. Predpokladajme teda, že máme
r-aproximačný algoritmus pre MaxClique a máme danú formulu ϕ ako vstup pre
Max-3-Sat. Z ϕ vyrobíme graf Gϕ nasledovným spôsoboom (viď. obr. ??): pre
každú klauzulu budeme mať skupinu 3 vrcholov, ktoré budú vzájomne pospájané
hranami. Navyše spojíme hranou všetky dvojice vrcholov zodpovedajúce literálu a
jeho negácii.
¬x1
x1
¬x2
x3
x2
x3
A
x2
x3
¬x1 ¬x2 x3
¬x1 ¬x2 x3
Obr. 4.1: Graf Gϕ a maximálna klika v doplnku Gϕ pre formulu (x1 ∨ x2 ∨ ¬x3 ) ∧
(¬x1 ∨ x2 ∨ x3 ) ∧ (¬x1 ∨ ¬x2 ∨ x3 ) ∧ (x1 ∨ ¬x2 ∨ x3 ). Vyznačená maximálna klika
zodpovedá ohodnoteniu x1 = 0, x2 = x3 = 1, ktoré splňuje 4 klauzuly.
R
Označme Gϕ doplnok grafu Gϕ . Nech K je maximálna klika v Gϕ . Každý vrchol v kliky K zodpovedá nejakému literálu lv . Zostrojme pravdivostné ohodnotenie
formuly ϕ tak, aby každý lv bol splnený. Toto zrejme ide urobiť, pretože nikdy sa
nevyskytne dvojica literál a jeho negácia. Zjavne, takéto ohodnotenie spĺňa |K| klauzúl. Keby sme teda mali r-aproximáciu MaxClique, mali by sme aj r-aproximáciu
Max-3-Sat.
D
Ukázali sme, že, z hľadiska aproximácie, je MaxClique aspoň tak ťažký ako
Max-3-Sat. V skutočnosti je ešte ťažší, ako vyplýva z nasledovnej vety:
Veta 4.4 Ak MaxClique ∈ APX, potom MaxClique ∈ PTAS.
Dôkaz: Predpokladajme, že máme algoritmus A, ktorý aproximuje MaxClique
s pomerom r. Ukážeme, ako v polynomiálnom čase nájdeme riešenie s pomerom
najviac r1/k pre ľubovoľnú konštantu k. Majme vstupný graf G = (V, E). Zostrojme
k nemu ”nafúknutý” graf Gk = (V k , E k ) nasledovne:
Vk
E
k
= {[v1 , . . . , vk ] | ∀i : vi ∈ V }
=
([v1 , . . . , vk ], [w1 , . . . , wk ]) | [v1 , . . . , vk ], [w1 , . . . , wk ] ∈ V k :
∀i : vi = wi ∨ (vi , wi ) ∈ E}
Vrcholy grafu Gk sú k-rozmerné vektory vrcholov grafu G, pričom dva vrcholy
sú spojené hranou, ak v každej súradnici sú buď rovnaké alebo susedné vrcholy
10 ledaže
11 t.j.
by platilo P = NP
nájsť najväčšiu skupinu vrcholov prepojených “každý s každým”
4.2. POUŽITIE PCPVETY
43
FT
pôvodného grafu. Zjavne ku každej klike C grafu G, existuje klika veľkosti |C|k v
grafe Gk : každé dva vrcholy Gk , ktorých všetky súradnice sú z C (takých vrcholov
je |C|k ) sú spojené hranou. Tvrdenie však platí aj naopak: ak máme v Gk kliku
C veľkosti |C| ≥ ck , potom existuje klika veľkosti c v G. Dôvod, prečo je to tak,
je jednoduchý: napíšme si všetky vrcholy C pod seba do tabuľky s |C| riadkami a
k stĺpcami. Keďže každé dva riadky sú rôzne, musí existovať stĺpec i, v ktorom je
aspoň c rôznych hodnôt12 . Vrcholy G v i-tom stĺpci ale tvoria kliku v G.
Majme ľubovoľnú konštantu k; zostrojíme r1/k -aproximačný algoritmus pre MaxClique: pre daný graf G vyrobíme Gk , nájdeme r-aproximáciu MaxClique a
pomocou predchádzajúcej konštrukcie nájdeme kliku v G. Nech mA je veľkosť kliky
nájdenej algoritmom A. Potom pre náš algoritmus platí:
m(G) ≥ mA (Gk )1/k
Zároveň ale pre optimálne riešenie platí
m∗ (Gk ) ≥ m∗ (G)k
Preto aproximačný pomer nášho algoritmu je
A
m∗ (Gk )1/k
m∗ (G)
≤
≤ r1/k
m(G)
mA (Gk )1/k
D
R
Z predchádzajúcich dvoch viet vyplýva, že ak P 6= NP, tak problém MaxClique
sa nedá aproximovať s konštantným aproxima4ným pomerom. Na druhej strane,
videli sme, že pre Max-3-Sat existuje konštantný aproximačný algoritmus.
12 S
použitím c hodnôt v každom stĺpci sa dá vyrobiť najviac ck rôznych riadkov.
KAPITOLA 4. NEGATÍVNE VÝSLEDKY O APROXIMÁCII
D
R
A
FT
44
Kapitola 5
FT
Redukcia a úplnosť v
triedach aproximovateľnosti
D
R
A
V časti 2.2 sme definovali Turigovu a Karpovu redukciu, ktoré umožňujú porovnávať optimalizačné problémy z hľadiska ich zložitosti. Naším cieľom v tejto kapitole
je nájsť pre danú triedu aproximácie “najťažší” problém, ktorý do nej patrí, a prirodzený spôsob, ako to dosiahnuť je pomocou pojmu úplnosti: problém P je pre
danú triedu úplný, ak sa ľubovoľný iný problém z danej triedy dá redukovať na P .
Chceme teda nájť problémy, ktoré by boli napr. NPo -úplné, APX-uplné.
Pripomeňme si Definíciu 2.4, podľa ktorej je trieda NPo trieda optimalizačných
problémov (I, SOL, m, c), pre ktoré existuje deterministický Turingov stroj, ktorý
pre dané x ∈ I a y v polynomiálnom čase zistí, či y ∈ SOL(x). Podľa Vety 2.3 je
každý optimalizačný problém, ktorého rozhodovacia verzia je NP-úplná, NPo -ťažký.
Stačí teda nájsť optimaliačný problém z NPo , ktorého rozhodovacia verzia je NPúplná. To sú ale všetky problémy, ktorými sme sa doteraz zaoberali! Problém je v
tom, že Turingova a Karpova redukcia sú pre naše účely príliš “hrubé”: my chceme
kategorizovať “ťažké” problémy z hľadiska aproximovateľnosti; spomínané redukcie
zhrnú všetky pre nás zaujímavé problémy do jednej triedy ekvivalencie. Potrebujeme preto jemnejší nástroj: redukciu, ktorá istým spôsobom zachováva vlastnosti
aproximácie. Pre naše účely budeme používať pojem AP-redukovateľnosti a vždy,
keď budeme hovoriť u úplných problémoch, budeme mať na mysli úplnosť vzhľadom
na AP-redukciu.
Čo vyžadujeme od AP-redukcie? Ak má byť problém P1 redukovateľný na problém P2 , potrebujeme mať funkciu f , ktorá prerobí vstup pre problém P1 na vstup
pre problém P2 , a funkciu g, ktorá prerobí riešenie problému P2 na riešenie problému P1 . Navyše, ak máme vstup x pre problém P1 , a y je dobrou aproximáciou
pre f (x) (v probléme P2 ), potom chceme, aby g(y) bolo dobrou aproximáciou pre
x (v probléme P1 ).
P1
P2
f
x
f (x)
1 + α(r − 1)
r
g(x, y)
g
y
Obr. 5.1: Schéma AP redukovateľnosti.
45
46KAPITOLA 5. REDUKCIA A ÚPLNOSŤ V TRIEDACH APROXIMOVATEĽNOSTI
AP-redukcia
Definícia 5.1 Majme dva problémy P1 = (I1 , SOL1 , m1 , c1 ) , P2 = (I2 , SOL2 , m2 , c2 ).
Povieme, že P1 je AP-redukovateľný na P2 ( P1 ≤AP P2 ), ak existuje konštanta
α > 1 taká, že pre každé r > 1 existujú funkcie fr a gr vypočítateľné v polynomiálnom čase1 také, že
1. x ∈ I1 ⇒ fr (x) ∈ I2
2. SOL1 (x) 6= ∅ ⇒ SOL2 (f (x)) 6= ∅
4. ∀x ∈ I1 ∀y ∈ SOL2 (fr (x)) :
FT
3. ∀y ∈ SOL2 (fr (x)) : gr (x, y) ∈ SOL1 (x)
RP2 (fr (x), y) ≤ r ⇒ RP1 (x, gr (x, y)) ≤ 1 + α(r − 1)
Kým prvé tri body predchádzajúcej definície sú technické podmienky na funkcie
f , g, hlavná idea je skrytá v bode 4: ak vieme problém P2 aproximovať s pomerom
r, redukcia nám dá aproximáciu problému P1 s pomerom 1 + α(r − 1) pre nejakú
konštantu α. Toto zodpovedá intuícii: pretože r > 1, člen r − 1 udáva, ako blízko je
daná aproximácia optimálnemu riešeniu. Redukcia môže túto vzdialenosť zväčšiť,
ale iba o konštantný násobok.
5.1
A
Lema 5.1 Ak P1 ∈ APX (resp. P1 ∈ PTAS) a P1 ≤AP P2 , tak P2 ∈ APX (resp.
P2 ∈ PTAS).
NPo -úplnosť
Definícia 5.2 Problém Max-weighted-Sat (alebo Max-W-Sat) má na vstupe
logickú formulu ϕ, pričom každej premennej xi je priradená váha w(xi ) ∈ N.
PCieľom
je nájsť pravdivostné priradenie π, ktoré spĺňa ϕ a zároveň maximalizuje
w(xi )
D
Max-W-Sat
R
V tejto časti budeme hľadať NPo -úplný problém, t.j. najťažšie aproximovateľný
problém z triedy NPo . Podľa Definície 2.4, pre každý NPo problém existuje deterministický Turingov stroj, ktorý pre daný vstup a dané riešenie v polynomiálnom čase
zistí, či je dané riešenie prípustné a zráta jeho cenu. Intuitívne najťažší problém
bude taký, kde samotné nájdenie akéhokoľvek prípustného riešenia je ťažké, nehovoriac už o nájdení dobrého riešenia. Vyberme si teda problém, pre ktorý povedať,
či existuje prípustné riešenie je NP-úplný problém. Príkladom takého problému je
nasledujúca verzia problému splniteľnosti2
xi =1
Zistiť, či existuje prípustné riešenie znamená zistiť, či ϕ je splniteľná. Ukážeme,
že problém Max-W-Sat je NPo -úplný. Urobíme tak v dvoch krokoch. najprv ukážeme, že ľubovoľný maximalizačný problém je redukovateľný na Max-W-Sat a
ľubovoľný minimalizačný problém je redukovateľný na Min-W-Sat (ktorý je definovaný analogicky). Potom ukážeme, že Min-W-Sat je redukovateľný na Max-WSat.
Lema 5.2 Problém Max-W-Sat je úplný pre triedu maximalizačných problémov z
NPo .
1 Vo všeobecnosti funkcie f a g závisia od r, a teda AP redukovateľnosť znamená: “Existuje
α taká, že ak P2 vieme aproximovať s faktorom r, potom vieme P1 aprixomovať s faktorom
1 + α(r − 1).”. V prípade, že f a g nezávisia od r, budeme index vynechávať.
2 pre zvyšok tejto kapitoly budeme logické hodnoty stotožňovať s číslami 0,1
5.1. NPO -ÚPLNOSŤ
47
FT
Dôkaz: Majme ľubovoľný maximalizačný problém P ∈ NPo . Nájdeme AP-redukciu
na Max-W-Sat pre α = 1. Vieme, že existuje deterministický Turingov stroj M ,
ktorý v polynomiálnom čase pre daný vstup x ∈ IP a y zistí, či y ∈ SOLP (x)
a vyráta m(x, y). Existuje teda aj nedeterministický Turingov stroj M 0 , ktorý na
vstupe x nedeterministicky uhádne y a simuluje M na vstupe x, y. Ak y 6∈ SOLP (x),
M 0 sa zacyklí, ináč na prvých s = q(|x|) políčkach pásky (kde q je polynóm z
Definície 2.4) zapíše binárny zápis m(x, y) a skončí.
Z Cook-Lewinovej vety vieme zostrojiť formulu ϕM 0 , ktorá je splniteľná práve
vtedy, ak M 0 zastaví a splňujúce pravdivostné ohodnotenie ϕM 0 definuje výpočet
M 0 . Nech v1 , . . . , vs sú premenné
PsϕM 0 , ktoré kódujú obsah prvých s políčok pásky
po skončení výpočtu M 0 , teda i=1 2s−i vi = m(x, y), pričom pre každé prípustné
riešenie y existuje príslušný výpočet M 0 .
Takže stačí v ϕM 0 priradiť váhy w(vi ) = 2s−i a váhy všetkých ostatých premenných nastaviť na 0. Riešenia Max-W-Sat takto ováhovanej ϕM 0 zodpovedajú
riešeniam problému P.
Analogicky ako predchádzajúcu lemu vieme dokázať aj fakt, že Min-W-Sat je
úplný pre triedu minimalizačných problémov z NPo . Z dôkazu navyše vyplýva, že
používame iba formuly istého typu:
A
Definícia 5.3 Obmedzený Min-W-Sat (R-Min-W-Sat) je problém Min-W-Sat,
v ktorom váhy premenných váhy spĺňajú nasledovnú vlastnosť: existuje nejaké s a
premenné v1 , . . . , vs s váhami w(vi ) = 2s−i ; všetky ostatné premenné majú váhu
0. Navyše každé pravdivostné ohodnotenie, ktoré spĺňa vstupnú formulu ϕ, nastaví
aspoň jednu premennú vi na 1.
Lema 5.3 Problém R-Min-W-Sat je úplný pre triedu minimalizačných problémov
z NPo .
Lema 5.4 R-Min-W-Sat ≤AP Max-W-Sat
R
Dôkaz: Majme vstup pre R-Min-W-Sat, t.j. formulu ϕ, ktorej premenné v1 , . . . , vs
majú váhy w(vi ) = 2s−i , teda hľadáme splňujúce ohodnotenie ϕ, ktoré nadobúda
min
s
X
2s−i vi
i=1
D
Chceme nájsť AP redukciu na Max-W-Sat, t.j. z ϕ vyrobiť inú (ováhovanú) formulu Ψ, ktorej maximálne splňujúce ohodnotenie dobre aproximuje minimálne splňujúce ohodnotenie ϕ. Keď si predstavíme premenné v1 , . . . , vs vo ϕ ako binárny
zápis čísla m, chceli by sme do Ψ zakódovať číslo 2s − m. Problém je v tom, že
máme k dispozícii iba výrokovú logiku, takže nemôžme priamočiaro zakódovať aritmetické operácie, a navyše musíme strážiť, aby veľkosť formuly narástla najviac
polynomiálne. Uspokojíme sa preto s aproximáciou hodnoty 2s − m.
Z didaktických dôvodov uvedieme najprv prístup, ktorý síce vedie k “AP” redukcii, ale parameter α nebude konštanta (bude závisieť od r). V druhom kroku
ukážeme, ako tento prístup spresniť a dostaneme hľadanú AP redukciu.
Predpokladajme, že i je najvýznamnejší nenulový bit v m. Potom zrejme m ∈
h2i , 2i+1 i a teda 2s − m ∈ h2s − 2i+1 , 2s − 2i i. S nádejou, že nám to snáď bude stačiť,
skúsme aproximovať m jeho najvyšším bitom; získame tak aproximáciu 2s − m v
intervale veľkosti 2i (t.j. s faktorom 2). Formulu Ψ vyrobíme tak, že k ϕ pridáme
s nových premenných z1 , . . . , zs pričom chceme, aby zi = 1 práve vtedy, ak prvý
nenulový bit v m je i. Formálne, zostrojíme funkciu f (ϕ) = Ψϕ , kde
Ψϕ = ϕ ∧
s
^
i=1
(zi ≡ v1 ∧ · · · ∧ vi−1 ∧ vi )
48KAPITOLA 5. REDUKCIA A ÚPLNOSŤ V TRIEDACH APROXIMOVATEĽNOSTI
Váhy premenných zi v Ψϕ sú w(zi ) = 2i a všetky ostatné premenné majú váhu 0.
Maximalizáciou Ψ získame ohodnotenie, ktoré maximalizuje pozíciu prvého nenulového bitu v m. Funkcia g z hľadanej redukcie bude jednoducho reštrikcia pravdivostného ohodnotenia Ψϕ na premenné z ϕ.
Teraz ideme ukázať, že takto definované funkcie f a g tvoria AP redukciu (t.j.
bod 4. Definície 5.1). Nech y je pravdivostné ohodnotenie Ψ, ktoré je r-aproximáciou
maxima. Zjavne v y je práve jedno zi = 1 a teda m(Ψ, y) = 2i . Zároveň platí, že
prvých i − 1 premenných vj je 0 a vi = 1, takže pre redukciou získané riešenie
R-Min-W-Sat platí:
2s−i ≤ m (ϕ, g(ϕ, y)) < 2 · 2s−i
FT
a teda
2s
2s
≤ m (ϕ, g(ϕ, y)) < 2
m(Ψ, y)
m(Ψ, y)
(5.1)
Zoberme si minimálne ohodnotenie π pre R-Min-W-Sat na ϕ a nech i je prvý nenulový bit m∗ (ϕ). Ohodnotenie π vieme doplniť na ohodnotenie π 0 pre Max-W-Sat
na Ψ jednoducho tak, že doplníme hodnoty premenných zi . Zjavne π 0 maximalizuje
pozíciu prvého bitu (keby existovalo riešenie Max-W-Sat na Ψ s prvým bitom viac
vpravo, príslušné riešenie R-Min-W-Sat na ϕ by bolo menšie). Pretože vzťah (5.1)
platí pre ľubovoľné ohodnotenie y, špeciálne pre y = π 0 dostaneme
m∗ (ϕ) ≥
2s
m∗ (Ψ)
A
teraz môžeme odhadnúť aproximačný pomer našej redukcie:
s
2
2 m(Ψ,y)
m (ϕ, g(ϕ, y))
m∗ (Ψ)
R (ϕ, g(ϕ, y)) =
<
=
2
= 2R(Ψ, y) = 2r
s
2
m∗ (ϕ)
m(Ψ, y)
m∗ (Ψ)
R
Podľa bodu 4. Definície 5.1 od AP redukcie vyžadujeme, aby 2r = 1 + α(r − 1), t.j.
α=
2r − 1
r−1
D
Vidíme, že takto definovaná redukcia nezachováva aproximačný pomer – s hodnotou
r blížiacou sa 1 α neobmedzene rastie.
Naša nádej, že riešenie R-Min-W-Sat stačí aproximovať najvyšším bitom sa
teda ukázala ako márna. Skúsme ho teda aproximovať k najvyššími bitmi (pričom
k zatiaľ ponecháme ako voľný parameter) tak, aby výsledná formula Ψ mala stále
veľkosť polynomiálnu od veľkosti ϕ. Namiesto premennej zi pridáme 2k premenných
zi:b1 ,...,bk . Budeme chcieť, aby zi:b1 ,...,bk vyjadrovala, že i-ty bit je 1 a nasledujúcich
k bitov má postupne za sebou hodnoty b1 , . . . , bk . Formula, ktorú vyrobí funkcia fk
bude vyzerať:
Ψϕ = ϕ∧
s
^
[zi:b1 ,...,bk ≡ (v1 ∧ · · · ∧ vi−1 ∧ vi ∧ (vi+1 ≡ d1 ) ∧ · · · ∧ (vi+k ≡ dk ))]
i=1,
[b1 ,...,bk ]∈Zk
2
V každom splňujúcom ohodnotení je práve jedna premenná zi:b1 ,...,bk splnená. Všetky
ostatné premenné budú mať váhu 0; ostáva rozhodnúť, ako nastaviť váhy premenným zi:b1 ,...,bk . Nech [b1 . . . bk ]2 označuje binárny zápi čísla b. Chceme nastaviť váhy
zi:b1 ,...,bk tak, aby Max-W-Sat našiel najpravejšiu hodnotu prvého nenulového bitu
(t.j. maximalizoval i) a spomedzi všetkých zi:b1 ,...,bk s touto hodnotou i vybral to s
minimálnym [b1 . . . bk ]2 .
Uvažujme výraz
2i+k
[vi . . . vi+k ]2
5.1. NPO -ÚPLNOSŤ
49
v5
0 0 0 0 1 0 1 1 ···
k=3
Obr. 5.2: Nech k = 3. Premenná z5:011 má váhu
25+3
[1011]2 .
FT
Zväčšenie hodnoty i o 1 zväčší celý výraz dvakrát. Pretože 2k ≤ [vi . . . vi+k ]2 < 2·2k ,
tento výraz je dobrý kandidát na váhu premennej zi:vi ...vi+k . Jediný problém je v
tom, že váhy muia byť celé čísla. Preto zvoľme
K2i+k
w(zi:b1 ...bk ) =
[b1 . . . bk ]2
A
Vhodnou voľbou K (napr. K 2s ) vieme zaručiť, že efekty zaokrúhľovania môžme
zanedbať.
Podobne ako v predchádzajúcich úvahách platí, že v každom splňujúcom ohodnotení Ψ je práve jedna premenná zi:b1 ...bk ) = 1 a
K2i+k
K2i
m(Ψ, y) = w(zi:b1 ...bk ) =
≈
Pk
[b1 . . . bk ]2
1 + j=1 bj 2−j
Pre riešenie R-Min-W-Sat potom dostaneme
m(ϕ, g(ϕ, y)) ≥ w(vi ) +
k
X
bj w(vi+j )
j=1
R
kde w(vi ) sú pôvodné váhy premenných vo ϕ a preto
s−i
m(ϕ, g(ϕ, y)) ≥ 2
1+
k
X
!
−j
bj 2
i=1
Na druhej strane
k
s
X
X
m(ϕ, g(ϕ, y)) ≤ w(vi )+
bj w(vi+j )+
D
j=1
Preto máme

w(vj ) < 2s−i 1 +
j=k+i+1
k
X

bj 2−j  1 + 2−k
j=1
K2s
K2s
≤ m(ϕ, g(ϕ, y)) <
1 + 2−k
m(Ψ, y)
m(Ψ, y)
a teda
R(ϕ, g(ϕ, y)) < 1 + 2−k R(Ψ, y)
Celá schéma AP redukcie bude vyzerať takto: predpokladajme, že vieme Max-WSat aproximovať s faktorom r > 1. Zvoľme k = dlog r − log(r − 1)e, t.j. 2−k ≤ r−1
r .
K danej formule ϕ zostrojme formulu Ψ podľa predchádzajúceho postupu; Ψ bude
mať polynomiálnu veľkosť. Získame riešenie Ψ, pre ktoré R(Ψ, y) ≤ r. Potom vieme,
že
R(ϕ, g(ϕ, y)) < 1 + 2−k R(Ψ, y) ≤ r + r2−k < 1 + 2(r − 1)
Máme teda AP redukciu s konštantou α = 2
Dokázali sme teda:
Veta 5.5 Problém Max-W-Sat je NPo -úplný.
50KAPITOLA 5. REDUKCIA A ÚPLNOSŤ V TRIEDACH APROXIMOVATEĽNOSTI
5.2
APX-úplnosť
Hľadajme teraz problém, ktorý by bol “najťažší” pre triedu APX, t.j. triedu problémov, ktoré vieme aproximovať s konštantným faktorom. V predchádzajúcich častiach sme ukázali, že problém Max-3-Sat 6∈ PTAS. Max-3-Sat je preto dobrý
kandidát na APX-úplný problém. Ak totiž ukážeme, že Max-3-Sat je APX-úplný,
t.j. že ľubovoľný problém z APX sa dá redukovať na Max-3-Sat, bude to aj znamenať, že žiaden APX-úplný problém nemá PTAS3
FT
Veta 5.6 Problém Max-3-Sat je úplný pre triedu maximalizačných problémov z
APX.
Dôkaz: Zoberme si ľubovoľný maximalizačný problém P ∈ APX. Vieme, že existuje
algoritmus AP a konštanta rP tak, že pre ľubovoľný vstup x problému P, algoritmus
AP vráti riešenie s cenou tP (x), pričom
tP (x) ≤ m∗P (x) ≤ rP tP (x)
R
A
Predpokladajme ďalej, že Max-3-Sat vieme aproximovať s faktorom r, t.j. pre
každú formulu Ψ v 3CNF vieme nájsť pravdivostné ohodnotenie y také, že R(Ψ, y) ≤
r. Naším cieľom je ukázať, že potom vieme problém P aproximovať s faktorom
1 + α(r − 1) pre nejakú konštantu α.
Kostra dôkazu je jednoduchá: pre vstup x problému P vyrobíme formulu Ψx
tak, že r-aproximácia splniteľnosti Ψ nám povie dosť veľa o optimálnom riešení
pre x. Prvý problém, ako zo vstupu x vyrobiť formulu, vyriešine aplikáciou CookLewinovej vety, podobne ako v dôkaze Lemy 5.2; dostaneme formulu ϕ, ktorej splniteľnosť nám dá informáciu o optimálnom riešení. Lenže splniteľnosť nevieme riešiť
optimálne, iba aproximovať (s faktorom r). Použijeme preto nástroj, ktorý sme vyrobili v dôkaze Vety 4.2: vieme totiž, že existuje konštanta ε taká, že pre ľubovoľný
jazyk L ∈ NP existuje funkcia f , ktorá pre každý vstup x vráti formulu f (x) v
3CNF takú, že
x ∈ L ⇒ f (x) jesplniteľná
x 6∈ L ⇒
v každom ohodnotení f (x) je aspoň ε−tina klauzúl nesplnená
D
Špeciálne ak za jazyk L zvolíme splniteľnosť, vieme z formuly ϕ vyrobiť formulu
Ψ = f (ϕ) tak, že Ψ je alebo splniteľná, alebo má aspoň ε-tinu nesplnených klauzúl.
Keby teda Ψ bola splniteľná a našli by sme 1 + ε aproximáciu splniteľnosti Ψ,
dostaneme splňujúce ohodnotenie. Prejdime teraz k detailnému dôkazu.
Pripomeňme, že máme maximalizačný problém P ∈ APX a algoritmus AP ,
ktorý pre ľubovoľné x vráti riešenie s cenou tP (x), pričom tP (x) ≤ m∗P (x) ≤
rP tP (x). Uvažujme ε z dôkazu Vety 4.2 a zvoľme
α = 2(rP log rP + rP + 1)
1+ε
ε
Nech Max-3-Sat vieme aproximovať s faktorom r, označme
rn = 1 + α(r − 1)
Chceme ukázať, že P vieme aproximovať s faktorom rn . Ak rP ≤ rn , samotný
algoritmus AP stačí na to, aby sme dosiahli rn aproximáciu. Predpokladajme teda,
že
rP > rn
3 Samozrejme,
všetky tieto tvrdenia sú za predpokladu, že P 6= NP.
5.2. APX-ÚPLNOSŤ
51
Vieme, že optimálne riešenie leží v intervale I = [tP (x), rp tP (x)]. Rozdeľme I na k
intervalov I0 , . . . , Ik−1 tak, aby pomer ich koncových bodov bol rn , t.j zvoľme
k = dlogrn rP e
a nech interval
Ii = rni tP (x), rni+1 tP (x)
m∗P (x)
n´a jden´e rieˇsenie
tP (x)
rni tP (x)
FT
Ii
rni+1tP (x)
rnk tP (x) ≥ rP tP (x)
Obr. 5.3: Hľadáme aproximáciu optimálneho riešenia – potrebujeme zistiť, v ktorom
intervale leží.
Ak zistíme, v ktorom z intervalov Ii leží optimálne riešenie (t.j. ak nájdeme
maximálne i také, že v intervale Ii leží nejaké riešenie) a nájdeme nejaké riešenie
z tohoto intervalu Ii , budeme mať hľadanú rn aproximáciu. Ako zistiť, či existuje
nejaké reišenie v intervale Ii ? Uvažujme nedeterministický Turingov stroj Mi :
R
A
Algoritmus 12 Nedeterministický Turingov stroj Mi
1: uhádni y
2: if y ∈ SOL(x) a mP (x, y) ∈ Ii then
3:
akceptuj x
4: else
5:
zacykli sa
6: end if
D
Platí, že Mi zastane na vstupe x práve vtedy, ak existuje riešenie s cenou z intervalu Ii . Nech ϕi je formula, ktorú dostaneme použitím Cook-Lewinovej vety na
stroj Mi , t.j. ϕi je splniteľná práve vtedy, ak Mi zastane a zo splňujúceho pravdivostného ohodnotenia ϕi sa dá zrekonštruovať nejaký (akceptujúci) výpočet Mi . Na
to, aby sme našli hľadanú rn -aproximáciu potrebujeme nájsť maximálne i také, že
ϕi je splniteľná; zo splňujúceho odhodnotenia ϕi potom zrekonštruujeme výpočet
Mi a príslušné riešenie bude hľadaná rn -aproximácia.
Nech Ψi = f (ϕi ) je formula v 3CNF, ktorú dostaneme použitím konštrukcie
z dôkazu Vety 4.2: Ψi je splniteľná práve vtedy, keď je splniteľná ϕi ; navyše, ak
Ψi je nesplniteľná, tak v ľubovoľnom ohodnotení je aspoň ε-tina jej klauzúl nesplnená. Preto ak nájdeme 1 + ε aproximáciu splniteľnosti Ψi , budeme vedieť rozhodnúť splniteľnosť ϕi . Naviac, zo splňujúceho pravdivostného ohodnotenia4 Ψi vieme
skonštruovať splňujúce pravdivostné ohodnotenie ϕi a teda akceptujúci výpočet Mi ,
ktorý nám dá rn -aproximáciu x. Potrebovali by sme teda zistiť 1 + ε aproximáciu
splniteľnosti pre všetky Ψi . Lenže podľa definície AP redukcie, máme k dispozícii
iba jedinú otázku na splniteľnosť. Definujme preto
Ψ=
k−1
^
Ψi
i=0
Bez ujmy na všeobecnosti môžeme predpokladať, že všetky Ψi majú rovnaký počet
u klauzúl. Zoberme r-aproximáciu splniteľnosti Ψ, t.j. pravdivostné ohodnotenie y
4 resp.
z jeho (1 + ε) aproximácie, čo je to isté
52KAPITOLA 5. REDUKCIA A ÚPLNOSŤ V TRIEDACH APROXIMOVATEĽNOSTI
také, že R(Ψ, y) = m∗ (Ψ)/m(Ψ, y) ≤ r. Vieme, že počet nesplnených klauzúl oproti
optimálnemu riešeniu je
m∗ (Ψ) − m(Ψ, y) ≤ m∗ (Ψ)
r−1
r−1
≤ ku
r
r
(5.2)
My ale potrebujeme garancie na splniteľnosť jednotlivých Ψi . Nech ri je aproximačný pomer splniteľnosti Ψi , ktorý dostaneme reštrikciou pravdivostného ohodnotenia y na klauzuly Ψi . Chceme ukázať, že ri ≤ 1 + ε. Vieme, že
m∗ (Ψ) − m(Ψ, y) ≥ m∗ (Ψi ) − m(Ψi , y) = m∗ (Ψi )
u ri − 1
ri − 1
≥
ri
2 ri
(5.3)
FT
Prvá nerovnosť vyjadruje najhorší prípad, že celá absolútna chyba aproximácie Ψ
sa dosahuje na klauzulách patriacich Ψi , posledná nerovnosť vyplýva z jednoduchého pozorovania, že polovica klauzúl je vždy splniteľná. Spojením (5.2) a (5.3)
dostaneme
r−1
u ri − 1
≤ ku
2 ri
r
a z toho úpravami
1
r−1
(5.4)
≥ 1 − 2k
ri
r
Pretože rn = 1 + α(r − 1), dostávame
rn − 1
+1
α
R
A
r=
Dosadíme z definície α = 2(rP log rP + rP + 1) 1+ε
ε a budeme mať
r=
rn − 1
ε
·
+1
2(1 + ε) rP log rP + rP − 1
(5.5)
Ďalej vieme, že
k
log rP
rn
+1≤
log rP + 1 =
log rn
rn − 1
rn log rP + rn − 1
rP log rP + rP − 1
<
rn − 1
rn − 1
= dlogrn rP e ≤
=
(5.6)
D
kde druhá nerovnosť vyplýva z Vety 1.8 a posledná z faktu, že rP > rn . Dosadíme
pravú stranu (5.6) do (5.5) a dostaneme
ε
r<
+1
2k(1 + ε)
a odtiaľ
2k(r − 1) >
ε
1+ε
Dosadíme do (5.4) a dostaneme hľadané
1
ε
r + ε(r − 1)
1
1
≥1−
=
·
≥
ri
(1 + ε)r
r
1+ε
1+ε
Dokázali sme teda nasledovné: ak máme r-aproximáciu splniteľnosti Ψ, vieme
z nej získať 1 + ε aproximáciu splniteľnosti Ψi a teda vieme, pre každý stroj Mi
povedať, či zastane. navyše, pre tie, ktoré zastanú, máme z ohodnotenia ϕi aj nejaký akceptujúci výpočet, t.j. nejaké prípustné riešenie z intervalu Ii , ktoré je rn aproximácia optimálneho riešenia problému P.
Dôkaz APX-úplnosti problému max-3-Sat ukončíme nasledujúcou vetou, z ktorej vyplynie, že aj všetky minimalizačné problémy z APX sú AP redukovateľné na
Max-2-Sat.
5.2. APX-ÚPLNOSŤ
53
Veta 5.7 Pre každý minimaliza4ný problém P ∈ APX existuje maximalizačný
problém P 0 ∈ APX taký, že P ≤AP P 0 .
Dôkaz: Nech A je r-aproximačn7 algoritmus riešiaci problém P a nech t(x) =
mP (x, A(x)). Definujme problém P 0 tak, že
t(x) + dre (t(x) − mP (x, y)) ak mP (x, y) ≤ t(x)
mP 0 (x, y) =
t(x)
inak
f (x)
= x
g(x, y) =
α
FT
Hľadaná AP redukcia potom bude
y
A(x)
= k+1
ak mP (x, y) ≤ t(x)
inak
Ostáva nám overiť definíciu AP redukcie, t.j. ak predpokladáme, že RP 0 (x, y) ≤ r0 ,
potrebujeme dokázať, že RcalP (x, g(x, y)) ≤ 1 + α(r0 − 1).
D
R
A
*** to do: dokončiť ***
D
R
A
FT
54KAPITOLA 5. REDUKCIA A ÚPLNOSŤ V TRIEDACH APROXIMOVATEĽNOSTI
Kapitola 6
FT
Problém obchodného
cestujúceho
Definícia 6.1 Majme daný úplný graf G = (V, E) s n vrcholmi, pričom každá hrana
e ∈ E má dĺžku ω(e). Cieľom je nájsť hamiltonovskú kružnicu K ⊆ E tak, aby sa
minimalizovala jej dĺžka, t.j.
X
min
ω(e)
A
e∈K
Veta 6.1 Ak P 6= NP, potom T SP 6∈ APX.
R
Dôkaz: Keby existoval r-aproximačný algoritmus A pre problém T SP , t.j. algoritmus, ktorý vráti hamiltonovskú kružnicu dĺžky m ≤ rm∗ , kde m∗ je dĺžka
najlacnejšej hamiltonovskej kružnice, potom ukážeme že P = NP. Uvažujme NPúplný problém hľadania hamiltonovskej kružnice v grafe. Pre daný graf G = (V, E)
vezmime úplný graf G0 = (V, E 0 ), pričom ω(e) = 1, ak e ∈ E, a ω(e) = 1 + nr, ak
e ∈ E 0 \E. Ak G má hamiltonovskú kružnicu, optimálne riešenie T SP (G0 ) má dĺžku
n a algoritmus A vráti hodnotu najviac nr. Ak G nemá hamiltonovskú kružnicu,
každé riešenie T SP (G0 ) má dĺžku aspoň 1 + nr.
Trojuholníková nerovnosť – Christofidesov algoritmus
D
6.1
Predchádzajúci výsledok nám nedáva veľkú nádej, že by sme našli efektívny aproximačný algortimus pre T SP . V skutočnosti sme ale ukázali iba to, že existujú
inštancie, ktoré sú ťažké. Stále však ostáva nádej, že inštancie, ktoré potrebujeme
v praxi riešiť, medzi ne nepatria. Ak sa bližšie pozrieme na inštancie z dôkazu
Vety 6.1, vidíme, že obsahujú veľmi dlhé aj veľmi krátke hrany. Skúsme takéto
“zlé” inštancie zakázať s cieľom dostať efektívny algoritmus pre čo možno najväčšiu
triedu inštancií.
V tejto časti sa obmedzíme na také inštancie T SP , ktorých ohodnotenia hrán
spĺňajú trojuholníkovú nerovnosť – t.j.
∀u, v, w ∈ V : ω (hu, vi) + ω (hv, wi) ≥ ω (hu, wi)
Takto ombedzenú úlohu budeme označovať ∆T SP . Ukážeme, že ťažké inštancie,
ktoré spôsobujú neaproximovateľnosť T SP sú také, ktoré porušujú trojuholníkovú
nerovnosť. Keď sa obmedzíme na inštancie s trojuholníkovou nerovnosťou, problém
začne byť aproximovateľný (aj keď stále ostáva NP-ťažký).
55
TSP
56
KAPITOLA 6. PROBLÉM OBCHODNÉHO CESTUJÚCEHO
FT
Algoritmus 13 Christofidesov algoritmus
1: majme úplný graf G = (V, E), |V | = n, každá hrana e ∈ E má dĺžku ω(e)
2: nájdi minimálnu kostru H grafu G
3: nech G0 ⊆ G je podgraf G indukovaný vrcholmi nepárneho stupňa z H
4: Edmondsovým algoritmom nájdi minimálny 1-faktor M grafu G0
5: nájdi Eulerov ťah R = (v0 , v1 , . . . , vm = v0 ) v grafe H ∪ M
6: K := (v0 )
7: for i from 1 to m do do
8:
if vi sa nevyskytuje v K then
9:
pripoj vi na koniec K
10:
end if
11: end for
12: pripoj v0 na koniec K
13: return K
Veta 6.2 Algoritmus 13 je 3/2-aproximačný algoritmus pre ∆T SP .
A
Dôkaz: Pre ľubovoľný podgraf X ⊆ G označme ω(X) súčet dĺžok všetkých hrán v
X. Nech m∗ je dĺžka optimálneho riešenia, t.j. dĺžka najkratšej hamiltonovskej kružnice. Algoritmus najprv na riadku 2 nájde minimálnu kostru H. Pretože vynechaním
ktorejkoľvek hrany z hamiltonovskej kružnice dostaneme kostru, cena minimálnej
kostry je určite menšia ako m∗ . Uvažujme teraz 1-faktor M z riadku 4. Chceme
ukázať, že ω(M ) < m∗ /2. Nech vrcholy grafu G0 (t.j. vrcholy nepárneho stupňa v
H) sú v1 , v2 , . . . , vk a nech sa, bez ujmy na všeobecnosti, v tomto poradí vyskytujú
v minimálnej hamiltonovskej kružnici G.
αk
vk
αk−1
vk−1
R
v1
α1
v2
α2
D
v3
α3
v4
Obr. 6.1: Cena minimálneho 1-faktora G0 je najviac m∗ /2.
Optimálne riešenie je teda kružnica v1 , α1 , v2 α2 , . . . , vk , αk (viď. Obr.6.1), kde
αi je cesta spájajúca vi a vi⊕1 . Z trojuholníkovej nerovnosti ale vyplýva, že ω(αi ) ≥
ω(hvi , vi⊕1 i), preto kružnica K 0 = (v1 , vk , . . . , vk ) má cenu ω(K 0 ) ≤ m∗ . Keďže k
je párne (sú to vrcholy nepárneho stupňa v H), kružnicu K 0 môžeme rozdeliť na
dva 1-faktory, z ktorých aspoň jeden má cenu najviac ω(K 0 )/2. Preto aj M ako
minimálny 1-faktor G0 má cenu najviac ω(K 0 )/2, t.j. najviac m∗ /2. Dokázali sme,
že ω(H) < m∗ a ω(M ) < m∗ /2, takže ω(H ∪ M ) < 3/2m∗ .
Graf H ∪ M má všetky vrcholy párneho stupňa1 , preto v ňom existuje Eulerov
ťah R, ktorého dĺžka je ω(H ∪ M ).
1 každý
vrchol, ktorý mal v kostre nepárny stupeň, má stupeň 1 v M
6.2. METRICKÝ TSP
57
FT
Obr. 6.2: Eulerovský ťah R a jeho skrátenie K.
Ostáva ukázať, že výsledná kružnica K, ktorá vznikla “skrátením” R, nemá
dĺžku väčšiu ako ω(R). Pri konštrukcii K sa vždy nahradila cesta v R jednou hranou,
preto z trojuholníkovej nerovnosti vyplýva trvdenie vety.
Pri dôkaze predchádzajúcej vety sme ukázali, že Christofidesov algoritmus má
aproximačný pomer ostro menší ako 3/2. Môžme teda dúfať, že šikovnejšou analýzou
dospejeme k lepšej konštante? Odpoveď je, žiaľ, negatívna, ako ukazuje nasledovná
veta:
1+ε
A
Veta 6.3 Pre každé kladné ε existuje inštancia ∆T SP , na ktorej Christofidesov
algoritmus vráti riešenie dĺžky m > 3/2m∗ − ε.
1+ε
R
1+ε
1+ε
D
Obr. 6.3: Zlý prípad pre Christofidesov algoritmus. Vyznačené čierne hrany majú
dĺžku 1, resp. 1+ε. Zvyšné hrany sú doplnené na maximálnu dĺžku, ktorá neporušuje
trojuholníkovú nerovnosť. Optimálne riešenie je červené a má dĺžku n + 4ε. Minimálna kostra je modrá a Christofidesov algoritmus ju doplní prerušovanou hranou.
Celková cena riešenia je 3/2n + c
6.2
Metrický TSP
V predchádzajúcej časti sme videli, že ak obmedzíme vstupné inštancie na také,
ktoré spĺňajú trojuholníkovú nerovnosť, existuje konštantný aproximačný algoritmus pre problém obchodného cestujúceho. Dá sa dúfať, že sa nám podarí nájsť
pre ∆TSP aj PTAS? Ako ukážeme neskôr, ∆TSP je príklad tzv. APX-úplného
problému, a preto je nepravdepodobné, že by pre neho existoval PTAS.
Skúsme teda pokračovať v obmedzovaní vstupných inštancií. Častokrát máme
totiž vstupné dáta, ktoré nielen spĺňajú trojuholníkovú nerovnosť, ale majú navyše aj geometrickú interpretáciu: vrcholy grafu zodpovedajú bodom v nejakom
Euklidovskom priestore a ohodnotenia hrán zodpovedajú vzdialenosti príslušných
58
KAPITOLA 6. PROBLÉM OBCHODNÉHO CESTUJÚCEHO
bodov. V tejto časti ukážeme, že T SP s takto obmedzenými inštanciami (budeme
ho nazývať metrický TSP) má PTAS.
Majme daných n bodov v rovine. Cieľom je nájsť čo najkratšiu TSP-cestu, t.j.
uzavretú lomenú čiaru, ktorá prechádza cez každý bod práve raz. V tejto časti
chceme ukázať, že pre každé c > 0 existuje polynomiálny
algoritmus, ktorý pre
každý vstup nájde TSP-cestu dĺžky najviac 1 + 1c · m∗ .
FT
S
Obr. 6.4: Idea rekurzívneho algoritmu
D
R
A
Hlavná myšlienka je použiť techniku rozdeľuj a panuj. Nech všetky body ležia vo
vnútri štvorca so stranou L. Štvorec si rozdelíme na štyri časti ako na Obr. 6.4; optimálna TSP-cesta tvorí v každom štvorci S množinu ciest M . Ak zafixujeme body,
v ktorých optimálna TSP-cesta vstupuje a vystupuje z S, potom M je množina
ciest, ktoré vstupujú a vystupujú z S v daných fixovaných bodoch, prechádzajú cez
všetky vstupné body vnútri S, a majú najmenšiu celkovú dĺžku spomedzi všetkých
ciest, ktoré spĺňajú prvé dve kritériá.
Keby sme teda vedeli uhádnuť, v ktorých miestach optimálna TSP-cesta pretína
deliace čiary, mohli by sme použiť jednoduchý rekurzívny algoritmus: na vstupe
budeme mať štvorec S a na jeho stranách postupnosť bodov, v ktorých ho optimálna TSP-cesta pretína. Množinu ciest, ktoré tvoria prienik optimálnej TSP-cesty
a S nájdeme tak, že rozdelíme S, ak je neprázdny, na štyri časti, uhádneme, kde
optimálna TSP-cesta pretína deliace čiary a rekurzívne zrátame štyri nezávislé podproblémy.
Pochopiteľne, problémom je uhádnuť priesečníky s deliacimi čiarami. V našom
prístupe sa preto obmedzíme na špeciálnu triedu TSP-ciest: budú to také, ktoré
môžu pretínať deliace čiary štvorcov iba v niektorých z dopredu daných bodov
nazývaných porty. Keďže portov bude málo, môžeme vyskúšať všetky možnosti ich
pretínania. Problému sme sa ale nezbavili: ako vieme, že optimálna (alebo aspoň
dosť dobrá) cesta je v nami uvažovanej triede? Kľúčovým bodom pre korektnosť
nášho algoritmu bude lema, ktorá bude zaručovať existenciu takýchto dosť dobrých
ciest. Na to, aby sme ju mohli vysloviť, potrebujeme najprv niekoľko definícií.
V ďalšom texte predpokladajme, že všetky body ležia v štvorci so stranou L a
majú celočíselné súradnice. Navyše bez ujmy na všeobecnosti nech L je mocnina 2.
Rekurzívnou procedúrou rozdelíme L vždy na štyri menšie štvorce, až sa dostaneme
k štvorcom veľkosti 1. Toto delenie si môžme predstaviť ako 4-árny strom, ktorého
koreň je L a štyria synovia každého štvorca sú 4 menšie štvorce, ktoré obsahuje. Na
celé delenie sa potom môžeme pozerať ako na mriežky rôznej hustoty poukladané
na sebe:
rekurzívne delenie
Definícia 6.2 Majme daný štvorec S so stranou L = 2k s ľavým dolným rohom v
bode [0, 0]. Nekonečnou mriežkou hustoty d nazveme množinu horizontálnych pria-
6.2. METRICKÝ TSP
59
FT
mok s y-ovými súradnicami i·d, i ∈ Z a vertikálnych priamok s x-ovými súradnicami
j · d, j ∈ Z.
Rekurzívnym delením L nazveme množinu k+1 štvorcových mriežok M0 , . . . , Mk ,
pričom Mi je prienikom nekonečnej mriežky hustoty L/2i a S. Budeme hovoriť, že
Mi je delením úrovne i a štvorce tvorené deliacimi priamkami z Mi budeme volať štvorce úrovne i. O deliacej čiare povieme, že je úrovne i, ak patrí do Mi , ale
nepatrí do žiadneho Mj , j < i.
Obr. 6.5: Rekurzívne delenie a príslušný quadtree. Najhrubšie čiary majú úroveň 1,
tenšie úroveň 2, najtenšie úroveň 3.
R
A
Rekurzívne delenie obsahuje L2 štvorcov úrovne log L, L2 /4 štovrcov úrovne
log L − 1, atď., až 1 štvorec úrovne 0, t.j. spolu O(L2 ) štvorcov. Pri implementácii
algoritmu je lepšie vynechať prázdne štvorce a používať dátovú štruktúru známu
ako quadtree. Quadtree vznikne rekurzívnym rozdelením pôvodného štvorca na 4
menšie ako v predchádzajúcom prípade, ale delenie nepokračuje po štvorce veľkosti
1, ale zastaví sa, akonáhl štvorec obsahuje najviac 1 bod. Quadtree má hĺbku log L
a každý list je buď neprázdny štvorec alebo susedí s neprázdnym štvorcom. Celkovo
máme teda O(n) listov a O(n log L) všetkých štvorcov. Pre jednoduchosť budeme
uvádzať algoritmus vo verzii pre rekurzívne delenia, úpravu pre quadtree nechávame
na čitateľa.
Teraz si vytipujeme porty, v ktorých bude môcť TSP-cesta pretínať deliace čiary:
D
Definícia 6.3 Uvažujme štvorec S so stranou L = 2k s ľavým dolným rohom v
bode [0, 0] a jeho rekurzívne delenie. Majme dané párne p > 0. p-portové rekurzívne
delenie S je rekurzívne delenie, v ktorom každá deliaca čiara úrovne i obsahuje porty
L
vo vzdialenostiach p2
i.
L/2i
L/p2i
Obr. 6.6: Porty na čiarach úrovne i a i + 1.
Ľahko vidno, že štvorec úrovne i má port v každom rohu a navyše na každej
hrane má maximálne p − 1 portov. Ako sme povedali, budú nás zaujímať iba také
TSP-cesty, ktoré pretínajú deliace čiary iba v portoch.
porty
60
KAPITOLA 6. PROBLÉM OBCHODNÉHO CESTUJÚCEHO
Definícia 6.4 Majme daný štvorec S so stranou L = 2k a jeho p-portové rekurzívne
delenie pre nejaké párne p > 0. TSP-cesta sa zavýva (p, r)-ľahká pre dané r > 0, ak
pretína každú hranu ľubovoľného štovrca delenia najviac r-krát, a to iba v portoch.
(p, r)-ľahká
TSP-cesta
Chceli by sme ukázať, že existuje nejaká (p, r)-ľahká TSP-cesta, ktorá dostatočne
dobre aproximuje optimálnu. Tvrdenie, ktoré ukážeme, však bude o niečo slabšie,
takže potrebujeme ešte jednu (poslednú) definíciu.
Definícia 6.5 Majme daný štvorec S so stranou L = 2k a jeho p-portové rekurzívne
delenie pre nejaké párne p > 0. Ďalej majme dané čísla a, b ∈ ZL . Rekurzívne delenie S s posunutím (a, b) dostaneme tak, že každú vertikálnu deliacu čiaru s x-ovou
súradnicou i nahradíme čiarou so súradnicou (i + a)mod L a každú horizontálnu
čiaru s y-ovou súradnicou j nahradíme čiarou so súradnicou (j + b)mod L.
FT
rekurzívne delenie s posunutím
A
Obr. 6.7: Rekurzívne delenie a posunuté rekurzívne delenie. Dva zodpovedajúce
štvorce sú vyplnené.
Lema 6.4 Majme danú ľubovoľnú konštantu c > 0 a vstup, v ktorom majú body
celočíselné súradnice, minimálna nenulová vzdialenosť medzi dvoma bodmi je aspoň
8 a všetky body ležia v štvorci so stranou dĺžky L = 2k . Nech a, b ∈ ZL sú náhodné
čísla vybraté nezávisle a rovnomerne. Potom existuje p = O(log L) a r = O(c)
také, že s pravdepodobnosťou aspoň 1/2 existuje (p, r)-ľahká TSP-cesta vzhľadom
na p-portové delelenie posunuté o (a, b), ktorá má dĺžku najviac 1 + 1c · m∗ , kde
m∗ je dĺžka optimálneho riešenia.
D
kľúčová lema
R
Pri posunutom delení budeme pokladať pôvodný štvorec za zacyklený, t.j. štyri
oblasti, na ktoré sa mohol rozpadnúť štvorec rekurzívneho delenia pri posunutí
budeme považovať za jeden štvorec.
Teraz budeme schopní vysloviť kľúčovú lemu týkajúcu sa existencie dostatočne
dobrých ľahkých ciest:
Dôkazu tejto lemy sa budeme venovať neskôr, najprv ukážeme, ako ju využiť pri
návrhu efektívneho algoritmu. V prveje fáze upravíme vstup tak, aby spĺňal podmienky lemy. V druhej fáze pre dané (a, b) pomocou dynamického programovania
nájdeme optimálnu (p, r)-ľahkú cestu. Vieme, že keby boli (a, b) vyberané náhodne,
s pravdepodobnosťou aspoň 1/2 bude nami nájdená cesta dobrá. Preto ak zopakujeme druhú fázu pre všetky možné dvojice a, b, určite dosť dobrú cestu nájdeme.
Celkový čas nášho algoritmu teda bude čas potrebný na úpravu vstupu a L2 -krát
čas potrebný na dynamické programovanie.
Predspracovanie vstupu
V tejto časti ukážeme, ako upraviť vstup tak, aby spĺňal podmienky Lemy 6.4.
Majme dané vstupné body X = (X1 , X2 , . . . , Xn ) a konštantu c > 02 . Najprv nájdeme štvorec S0 , v ktorom všetky body ležia. Nech má stranu dĺžky L0 . Potom
2 Navrhujeme
PTAS, t.j. chceme nájsť 1 +
1
c
-optimalizačný algoritmus.
6.2. METRICKÝ TSP
61
posunieme všetky body tak, aby S0 mal ľavý dolný roh v bode [0, 0]. Uvažujme
L0
nekonečnú mriežku hustoty 8nc
a posuňme každý bod vstupu k najbližšiemu mrežovému bodu3 . Takto upravené riešenie označme X 0 = (X10 , . . . , Xn0 ).
Ukážeme, že ak zostrojíme PTAS pre takto upravené problémy, máme zároveň
PTAS pre pôvodné problémy. Predpokladajme, že máme nejaké riešenie Y 0 vstupu
X 0 , ktoré navštívi posunuté body v poradí Xi01 , Xi02 , . . . , Xi0n a má celkovú dĺžku m0 .
Uvažujme riešenie Y vstupu X, ktoré navštívi pôvodné body v rovnakom poradí,
t.j. Xi1 , Xi2 , . . . , Xin . Aká je dĺžka Y ?
FT
Xj
Xj0
Xi0
Xi
Obr. 6.8: Predĺženie cesty pri posunutom vstupe
A
Každá úsečka Xi0 , Xj0 z Y 0 , ktorá prispievala do m0 dĺžkou d, sa nahradí úsečkou
Xi , Xj . Jej dĺžka je určite najviac dĺýka cesty Xi , Xi0 , Xj0 , Xj , čo určite nie je viac ako
m0 + L0 /4nc. Preto dostávame, že dĺžka Y je najviac m0 + n · L0 /4nc = m0 + L0 /4c.
Rovnaké úvahy platia aj naopak: ak máme nejaké riešenie Y vstupu X, potom
z neho vieme urobiť riešenie Y 0 vstupu X 0 dĺžky najviac m + L0 /4c, kde m je dĺžka
Y . Špeciálne ak zoberieme optimálne riešenie Y , dostaneme
R
m∗ (X 0 ) ≤ m∗ (X) +
L0
4c
Predpokladajme teraz, že vieme aproximovať posunuté riešenie s aproximačným
pomerom s, t.j. máme riešenie Y 0 , pre ktoré platí
m0 ≤ s · m∗ (X 0 )
D
Z neho vieme dostať riešenie Y pre pôvodný vstup, pre ktoré platí
L0
L0
L0
1
m ≤ m0 +
≤ sm∗ (X 0 ) +
≤ sm∗ (X) +
(1 + s) ≤ m∗ (X) s + (1 + s)
4c
4c
4c
4c
pretože m∗ (X) > L0 . To znamená, že ak chceme aproximovať pôvodný vstup s
pomerom 1 + 1c , stačí nám vedieť aproximovať upravený vstup s pomerom s, pre
ktorý platí
1
1
s + (1 + s) = 1 +
4c
c
t.j.
2
s=1+
4c + 1
Preto stačí, ak sa zostrojíme PTAS pre posunuté vstupy.
Fáza predspracovania vstupu teda spočíva v posunutí bodov a v zvýšení pres2
nosti aproximácie z 1+ 1c na 1+ 4c+1
. Na záver naškálujeme4 celý vstup tak, že všetky
3 Možno
4 toto
sa nám viac bodov namapuje do jedného mrežového bodu, ale to nám nevadí
škálovanie nemení aproximačný pomer
62
KAPITOLA 6. PROBLÉM OBCHODNÉHO CESTUJÚCEHO
súradnice prenásobíme koeficientom 64nc/L0 . Tým dostaneme inštanciu, v ktorej
súradnice bodov sú celočíselné a minimálna nenulová vzdialenosť medzi bodmi je
aspoň 8. Navyše, všetky body nového vstupu ležia v štvorci so stranou L = O(nc).
Dynamické programovanie
FT
V tejto časti uvažujme inštancie, ktoré spĺňajú podmienky Lemy6.4, t.j. body majú
celočíselné súradnice a minimálna nenulová vzdialenosť medzi bodmi je aspoň 8.
Ukážeme, ako pre dané p, r a posunutie a, b nájsť optimálnu (p, r)-ľahkú cestu
vzhľadom na dané posunutie. Podľa predchádzajúcich úvah predpokladajme, že
L = O(nc), p = O(c log L) a r = O(c). Keď budeme hovoriť o rekurzívnom delení,
budeme mať vždy na mysli delenie posunuté o (a, b).
Ako sme spomínali v úvode, na to, aby sme vedeli nájsť časť riešenia ležiacu v
nejakom štvorci S, potrebujeme uhádnuť, v ktorých miestach optimálna TSP-cesta
pretína hrany S. Uhádnuť to síce nevieme, ale keďže tieto priesečníky môžu byť iba
v portáloch, vyskúšame všetky možnosti. Budeme riešiť problém, kde vstupom je
1. štvorec S na úrovni l rekurzívneho rozdelenia
2. postupnosť portálov (môžu sa aj opakovať) a1 , a2 , . . . , a2q na hranách S tak,
že na každej hrane S je najviac r z nich5 .
Cieľom je nájsť množinu ciest P1 , . . . , Pq ležiacich v S takú, že
A
1. Pi začína v a2i−1 a končí v a2i
2. spolu prechádzajú cez všetky vstupné body v S
3. majú minimálnu celkovú dĺžku
D
R
Náš algoritmus bude postupovať od najvyšších úrovní až po úroveň 0. Pre každý
štvorec danej úrovne si budeme pamätať optimálne riešenia všetkých možných
vstupných inštancií (t.j. všetkých postupností portálov a1 , a2 , . . . , a2q spĺňajúcich podmienky zadania). Pre jeden štovrec delenia teda budeme uvažovať O (4p)4r · (4r)!
možností: na obvode štvorca je najviac 4p portov (viď. Obr. 6.6), z ktorých vyberáme
P4r
najviac 4r, čo je i=0 (4p)i = O (4p)4r možností. Navyše, pri každej možnosti je
najviac (4r)! utriedení portálov.
Štvorce na poslenej úrovni sa vyriešia ľahko, keďže obsahujú najviac jeden bod:
pre danú inštanciu uvažujeme úsečky spájajúce body a2i−1 a a2i , postupne každú z
nich nahradíme lomenou čiarou prechádzajúcou cez vnútorný bod, a nájdeme minimum. Predpokladajme teraz, že máme riešenia všetkých inštancií štvorcov úrovne
l. Zoberme si štvorec S na úrovni l − 1 a nejakú vstupnú inštanciu na ňom.
Uvažujme štyri štvorce S1 , . . . , S4 úrovne l vnútri S. Ak chceme vybaviť všetky
možné (p, r)-ľahké TSP-cesty, potrebujeme uvažovať všetky možné postupnosti b1 , . . . , bw
portov na vnútorných deliacich hranách. Každá hrana každého štvorca Si je (p, r)ľahkou TSP-cestou preťatá najviac r-krát a nachádza sa na nej p portov. Na každej zo štyroch vnútorných deliacich hrán najviac r vybratých portov, čo je spolu
O(p4r ) možností. Pre každý výber musíme uvažovať najviac (4r)! poradí a najviac
(4r)4r možností, ako vložiť postupnosť bi do postupnosti ai . Celkovo teda máme
O p4r (4r)!(4r)4r možností, pričom každá možnosť určuje jednu vstupnú inštanciu
v každom zo štovrcov S1 , . . . , S4 . Riešenia týchto inštancií nájdeme v príslušných
poliach a tak zistíme optimálne reišenie pre danúinštanciu štvorca S.
V každom štvorci uvažujeme O (4p)4r · (4r)! vstupných
inštancií, pričom na
máme O(L2 ) štvorspracovanie jednej inštancie treba časO p4r (4r)!(4r)4r . Spolu
4r
2
cov, takže celkový čas algoritmu je O L2 16p2 r [(4r)!] , čo pre konštantné c je
O n2 (log n)O(1) .
5 Každá inštancia teda obsahuje najviac 4r portálov. Inštancia s prázdnou postupnosťou v
štvorci úrovne 0 je hľadané riešenie.
6.2. METRICKÝ TSP
63
a4
a2
b4
a1
a3
b3
b1
b2
b5
FT
a5
a6
Obr. 6.9: dynamické programovanie
Dôkaz kľúčovej lemy
R
A
V tejto časti ukončíme analýzu nášho algoritmu tým, že dokážeme Lemu 6.4. Pri
dôkaze budeme vychádzať z optimálnej TSP-cesty, ktorú budeme postupne upravovať tak, aby sa stala (p, r)-ľahkou. Pri týchto úpravách sa cesta predĺži a tieto
predĺženia budeme musieť držať pod kontrolou. Pri prerábaní optimálnej cesty na
(p, r)-ľahkú musíme zabezpečiť dve veci – aby počet priesečníkov na hrane každého
štvorca bol najviac r, a aby tieto priesečníky boli iba v portoch.
Na redukciu počtu priesečníkov budeme používať nasledovnú lemu6 :
Lema 6.5 Nech S je úsečka dĺžky s a π je uzavretá krivka, ktorá pretína S v t > 2
bodoch. Potom existuje množina podúsečiek úsečky S s celkovou dĺžkou najviac 6s,
ktorých pridaním do π vznikne uzavretá krivka π 0 , ktorá pretína S najviac dvakrát.
D
Dôkaz: Nech t je párne (dôkaz pre t nepárne je analogický) a nech P1 , . . . , Pt sú
príslušné priesečníky. Zoberme dve kópie priesečníkov: P1 , . . . , Pt a P10 , . . . , Pt0 . O Pi
budeme hovoriť ako o “horných” a o Pi0 ako o “dolných” priesečníkoch. Pridajme
úsečky P1 Pt , P1 P2 , P2 P3 , . . . , Pt−2 Pt−1 a úsečky P2 P3 , P4 P5 , . . . Pt−2 Pt−1 a analogicky pre body Pi0 . Situácia bude ako na Obr. 6.10, kde sú kvôli názornosti body
Pi a Pi0 odsunuté od S a podúsečky sú kreslené ako oblúky. Celková dĺžka úsečiek
pridaných na jednej strane je najviac 3s. Navyše, cesta π po pridaní úsečiek tvorí
graf párneho stupňa, v ktorom existuje eulerovský ťah. Tento ťah zodpovedá ceste
π 0 , ktorá pretína S práve dvakrát.
Majme teraz vstup s n bodmi ležiacimi v štvorci S so stranou L. Uvažujme
mriežku M hustoty 1 položenú na S 7 . Aby sme udržali prehľad o celkovom pred´žení
pri úpravách cesty, budeme každé vzniknuté predĺženie účtovať niektorej (horizontálnej alebo vertikálnej) čiare M . V ďalšom budeme t(π, l) označovať počet priesečníkov TSP-cesty π a nejake deliacej čiary z M . Pri analýze tohto účtovania budeme
používať lemu, ktorá dáva do súvisu dĺžku cesty a počet priesečníkov.
Lema 6.6 Majme vstup v ktorom najmenšia vzájomná vzdialenosť dvoch bodov je
aspoň 4 a TSP-cestu π, ktorej dĺžka je T . Potom platí
X
X
t(π, l) +
t(π, l) ≤ 2T
l je vertikálna
6 známu
7 zrejme
l je horizontálna
pod menom Patching lemma
každá deliaca čiara rekurzívneho delenia patrí do M
64
KAPITOLA 6. PROBLÉM OBCHODNÉHO CESTUJÚCEHO
P1
P2
Pt
Pt0
P20
FT
P10
Obr. 6.10: Dôkaz Lemy 6.5 pre párny počet priesečníkov.
kde l označuje čiary z M .
A
Dôkaz: Zoberme si jednu úsečku S dĺžky s z π a skúmajme,√koľko je jej vklad do
ľavej strany. Intuitívne je to zhruba `1 norma, čo je najviac s. Formálne, ak u a
v sú dĺžky priemetov S na x-ovú a y-ovú os, t.j. s2 = u2 + v 2 , vklad S do ľavej
strany je najviac
1). Vieme, že paltí8 (u + v)2 ≤ 2(u2 + v 2 ), preto
p (u + 1) + (v + √
2
2
u + v + 2 ≤ 2(u + v ) + 2 = s 2 + 2. Keďže s ≥ 4, máme u + v + 2 ≤ 2s.
R
Teraz môžme dokázať kľučovú lemu:
Dôkaz Lemy 6.4:
Zvoľme si s = 72c a p = 2s log L, pričom L = O(nc) je
veľkosť štvorca, v ktorom ležia všetky body. Nech π je optimálna TSP-cesta a nech
a, b ∈ ZL sú zvolené náhodne. Uvažujme čiary rekurzívneho delenia – pre každú
úroveň i máme 2i horizontálnych a 2i vertikálnych čiar na úrovni i. Keďže a, b sú
volené náhodne, je pre každú čiaru l
P r[l je na úrovni i] =
2i
L
D
Budeme postupne upravovať π, aby sa stala (p, s + 4)-ľahkou9 . Pri týchto úpravách každé predĺženie cesty budeme účtovať nejakej deliacej čiare, pričom pre každú
čiaru l bude platiť
E a,b [celkové predĺženie účtované l] ≤
t(π, l)
4c
(6.1)
kde t(π, l) je počet priesečníkov π s čiarou l a stredná hodnota je braná cez náhodnú
voľbu parametrov a, b. Ak sa nám podarí ukázať (6.1), vyhlásime dôkaz za hotový,
lebo z linearity strednej hodnoty dostaneme, že
E a,b [celkové predĺženie] ≤
X
l je vertikálna
t(π, l)
+
4c
X
l je horizontálna
t(π, l)
4c
a podľa Lemy 6.6 máme
E a,b [celkové predĺženie] ≤
8 dôkaz
m∗
2c
prenechávame na čitateľa ako cvičenie
tým, že sa budeme snažiť vyrobiť (p, s)-ľahkú cestu, ale nakoniec sa ukáže, že potrebujeme povoliť 4 ďalšie priesečníky.
9 Začneme
6.2. METRICKÝ TSP
65
FT
Podľa Markovovej nerovnosti je potom s pravdepodobnosťou 1/2 celkové predĺženie
najviac m∗ /c a teda s pravdepodobnosťou aspoň 1/2 existuje (p, s + 4)-ľahká cesta
s cenou najviac (1 + 1/c)m∗ .
Ako upraviť π, aby sa stala (p, s)-ľahkou? Treba, aby pretínala každú hranu
každého štvorca najviac s-krát a aby tieto priesečníky boli v portoch. Zoberme si
vertikálnu10 čiaru l na úrovni i. Najmenší
i,
štvorec, ktorý sa jej dotýka má úroveň
preto stačí najprv na každom intervale b + k 2Li mod L, b + (k + 1) · 2Li mod L (viď.
Obr. 6.6) zredukovať pomocou Lemy 6.5 počet priesečníkov na s a potom tieto
priesečníky posunúť do najbližšieho portu.
Priamočiare použitie Lemy 6.5 by však mohlo natiahnuť dĺžku príliš. Preto použijeme procedúru Modify (Algoritmus 14)
Algoritmus 14 procedúra Modify(l, i, b)
1: vstup: čiara l na úrovni i, cesta π a vertikálne posunutie b
2: for j = log L down to i do
3:
for k = 0
to 2j − 1 do
4:
I := b + k · 2Li mod L, b + (k + 1) · 2Li mod L
5:
ak π pretína I viac ako s-krát, pomocou Lemy 6.5 zredukuj počet priesečníkov na 4
6:
end for
7: end for
R
A
Prv než budeme pokračovať v dôkaze sú namieste dve poznámky. V riadku 5
sa počet priesečníkov redukuje na 4 a nie na 2 preto, že rohové zacyklené štvorce
vytvárajú nezávislé oblasti a v takých potrebujeme lemu aplikovať dvakrát. Druhá
poznámka sa týka vzťahu horizontálnych a vertikálnych čiar: úprava cesty pre horizontálnu čiaru môže zvýšiť počet priesečníkov na vertikálnej čiare. Toto zvýšenie
sa ale dá s pomocou Lemy 6.5 ošetriť tak, že na každom intervale pribudnú najviac
4 priesečníky.
*** to do: podrobnejšie? ***
Poďme teraz analyzovať procedúru Modify. Fixujme si čiaru l a označme cl,j (b)
počet segmentov, na ktoré sme aplikovali Lemu 6.5 v j-tej iterácii Modify(l, i, b).
Cesta π pretína l t(π, l)-krát a každá aplikácia lemy nahradí aspoň s+1 priesečníkov
najviac štyrmi. Preto
X
t(π, l)
cl,j (b) ≤
s−3
j≥1
D
Zároveň podľa Lemy 6.5 každé volanie Modify(l, i, b) predĺži π najviac o
X
cl,j (b)
j≥1
6L
2j
a toto predĺženie účtujeme l. Pretože pravdepodobnosť, že l je na úrovni i, a teda
voláme Modify(l, i, b), je najviac 2i /L (vzhľadom na náhodnú voľbu a), pre fixné
b dostávame
E a [zaúčtované čiare l]
=
X 2i
i≥1
≤
· cena Modify(l, i, b) ≤
X 2i X
X cl,j (b) X
6L
·
cl,j (b) j = 6 ·
·
2i ≤
L
2
2j
i≥1
10 rovnaké
L
j≥i
argumenty platia pre horizontálne čiary
j≥1
i≤j
66
KAPITOLA 6. PROBLÉM OBCHODNÉHO CESTUJÚCEHO
≤
12 ·
X
cl,j (b) ≤
j≥1
12t(π, l)
s−3
FT
Ďalej treba každý priesečník posunúť na najbližší port. Urobíme to tak, že nebudeme meniť úsečku patriacu TSP-ceste, ale pridáme dva úseky ležiace na deliacej
čiare ako na Obr. 6.11.
Obr. 6.11: Presun priesečníka na najbližší port
Pre čiaru l na úrovni i každý z t(π, l) priesečníkov musí byť posunutý o najviac
L/(2i+1 p), prete celkové predĺženie v tejto fáze je najviac
log
XL
A
i=1
L
t(π, l) log L
2i
t(π, l) i =
L
2p
p
Keďže p ≥ 2s log L, je pravá strana najviac t(π, l)/2s. Celkovo teda jednej čiare
zaúčtujeme najviac
12t(π, l) t(π, l)
t(π, l)
+
≤
s−3
2s
4c
Stabilita aproximácie
R
6.3
D
Videli sme, že všeobecná verzia TSP sa nedá dobre aproximovať, ale inštancie spĺňajúce trojuholníkovú nerovnosť sú “ľahké”. Takéto rozdelenie na dve skupiny je však
dosť hrubé. Intuícia vraví, že inštancie, ktoré “takmer” spĺňajú trojuholníkovú nerovnosť by stále mali byť rozumne aproximovateľné. Túto ideu formalizuje pojem
stability aproximácie:
stabilita
aproxmácie
Definícia 6.6 Majme optimalizačný problém P = (I, SOL, m, c). Uvažujme podmnožinu vstupných inštancií I 0 ( I a polynomiálne vypočítateľnú vzdialenostnú
funkciu h : I 7→ R≥0 takú, že ∀x ∈ I 0 : h(x) = 0. Guľa polomeru δ je množina
vstupov, ktoré sú od I 0 vzdialené najviac δ, t.j. Γδ,h (I 0 ) = {x ∈ I | h(x) ≤ δ} Majme
algoritums A, ktorý je r-aproximačný pre problém P 0 = (I 0 , SOL, m, c). A nazveme
s-stabilný , ak pre každé s0 ≤ s existuje r0 tak, že A je r0 -aproximačný pre problém
(Γs0 ,h (I 0 ), SOL, m, c).
A je stabilný, ak je s-stabilný pre každé s > 0.
Funkcia h rozbíja vstupné inštancie na (potenciálne nekonečne veľa) tried, ktoré
majú rovnakú vzdialenosť od I 0 . Algoritmus je vzhľadom na h stabilný vtedy, ak
aproximačný pomer je pre inštancie v jednej triede konštantný. Samozrejme, na to,
aby pojem stability mal zmysel, potrebujeme vhodnú funkciu h.
Ako porovnať, či je nejaká inštancia “blízko” trojuholníkovej nerovnosti? Prirodzené by bolo zobrať funkciu dist, ktorá meria ako veľmi je trojuholníková nerovnosť
porušená v jednom trojuholníku:
6.3. STABILITA APROXIMÁCIE
67
dist(x) = max 0, max
u,v,w∈V
ω(hu, vi)
−1
ω(hu, wi) + ω(hw, vi)
FT
Skúsme teraz analyzovať Christofidesov algoritmus vzhľadom na funkciu dist.
Kde sa v dôkaze Vety 6.2 využívala trojuholníková nerovnosť? Bolo to pri záverečnom skracovaní Eulerovho ťahu R na kružnicu K, a pri argumentácii, že cena
1-faktora M je najviac m∗ /2. V oboch prípadoch sme trojuholníkovú nerovnosť
použili na to, aby sme cestu nahradili jednou hranou.
Majme teraz inštancie x také, že dist(x) ≤ s. Chceli by sme ukázať, že Christofidesov algoritmus je stabilný, t.j. že aproximačný pomer je konštanta, ktorá závisí
iba od s. Podľa definície dist máme, že
∀u, v, w ∈ V : ω(hu, vi) ≤ (1 + s) [ω(hu, wi) + ω(hw, vi)]
Ak máme cestu s m vrcholmi a nahradíme dždy dve susedné hrany jednou, dostaneme cestu s dm/2e vrcholmi a jej cena bude najviac (1 + s)-násobok ceny pôvodnej
cesty. Po dlog ne krokoch dostaneme jednu hranu, preto môžme v dôkaze Vety 6.2
upraviť
m = ω(K) ≤ (1 + s)dlog ne ω(H ∪ M )
kde
1
(1 + s)dlog ne m∗
2
A
ω(M ) ≤
Preto
1
m ≤ (1 + s)dlog ne 1 + (1 + s)dlog ne m∗ = O n2 log(1+s) m∗
2
R
Vidíme, že aproximačný pomer nie je konštanta, takže sa nám nepodarilo ukázať,
že Christofidesov algoritmus je stabilný. Je to iba naša nešikovnosť? Nie, lebo vieme
ukázať, že predchádzajúca analýza sa nedá príliš zlepšiť.
4(1 + s)2
D
2(1 + s)
1
1
4(1 + s)2
2(1 + s)
1
1
2(1 + s)
2(1 + s)
1
1
2(1 + s)
4(1 + s)2
4(1 + s)2
2(1 + s)
1
1
2(1 + s)
4(1 + s)2
1
1
2(1 + s)
4(1 + s)2
n(1 + s)log n
Obr. 6.12: Christofidesov algoritmus je nestabilný vzhľadom na dist
Uvažujme graf na Obr. 6.12 (b.u.n.v. nech n je mocnina dvoch). Zafixujme si
cestu P = v1 , v2 , ..., nn dĺžky n. Každej hrane tvaru e = hvi , vi+2k i priradíme váhu
ω(e) = 2k (1 + s)k . Ostatné váhy dodefinujeme tak, aby dist(x) ≤ s. Minimálna
kostra je P , preto cena Christofidesovho algoritmu je m = n+n(1+s)log n . Kružnica,
ktorá používa iba hrany tvaru hvi , vi+2 i a hrany hv1 , v2 i, hvn−1 , vn i má cenu 2(n −
2)(1 + s) + 2. Preto
68
KAPITOLA 6. PROBLÉM OBCHODNÉHO CESTUJÚCEHO
m
n + n(1 + s)log n
n1+log(1+s)
nlog(1+s)
≥
≥
=
m∗
2(n − 2)(1 + s) + 2
2n(1 + s)
2(1 + s)
FT
Christofidesov algoritmus teda nie je stabilný vzhľadom na dist a ostáva otázka,
čo sa s tým dá ďalej urobiť. Nestabilita vyplýva z toho, že funkcia dist meria iba
“lokálne” porušenia trojuholníkovej nerovnosti, čo spôsobuje problém pri odhade
skracovania cesty. Zadefinujme si preto inú funkciu dist2 , ktorá bude merať predĺženie pre všetky cesty P .
ω(hv1 , vm+1 i)
P
−1
dist2 (x) = max 0,
max
m
P =v1 ,...,vm+1
i=1 ω(hvi , vi+1 i)
Funkcia dist2 nám umožní vysloviť nasledujúcu vetu:
Veta 6.7 Christofidesov algoritmus je stabilný vzhľadom na funkciu dist2 .
Dôkaz: Podobne ako v predchádzajúcich úvahách majme inštancie x, kde dist2 (x) ≤
s. Zmeny, ktoré sú potrebné urobiť v dôkaze Vety 6.2 sú
m = ω(K) ≤ (1 + s) · ω(H ∪ M )
kde
1
(1 + s)m∗
2
A
ω(M ) ≤
D
R
Tento výsledok ukazuje, že Christofidesov algoritmus sa dá úspešne použiť aj na
vstupoch, ktoré síce trojuholníkovú nerovnosť nespĺňajú, ale príliš sa od nej nelíšía.
Toky a rezy
FT
Kapitola 7
V tejto časti sa budeme venovať dvom typom problémov, ktoré spolu úzko súvisia.
Jedným typom sú problémy týkajúce sa toku v grafe, konkrétne hľadania maximálneho toku. Druhý typ problémov sú varianty hľadania minimálneho hranového rezu.
Pripomeňme základné pojmy:
Max-Flow
A
Definícia 7.1 Majme daný graf G = (V, E), v ňom dva význačné vrcholy s, t a
funkciu c : E 7→ Q+ udávajúcu kapacitu hrán. Funkciu f : V × V 7→ Q+ nazveme
s − t tok, ak
1. ak (u, v) 6∈ E alebo u = v, tak f (u, v) = 0
R
2. ∀e = (u, v) ∈ E : f (u, v) + f (v, u) ≤ ce
P
P
3. ∀u 6= s, t :
v∈V f (u, v) =
v∈V f (v, u)
P
P
Veľkosť toku f je u∈V f (u, t) − u∈V f (t, u). Problém Max-Flow vyžaduje nájsť
pre dané, G, s, t, e tok maximálnej veľkosti.
D
Definícia 7.2 Majme daný graf G = (V, E), v ňom dva význačné vrcholy s, t a
funkciu c : E 7→ Q+ udávajúcu cenu hrán. Hranový s − t rez je množina hrán
E 0 ⊆ E taká, že vrcholy s a t sú v rôznych komponentoch súvislosti grafu G − E 0 .
veľkosť rezu je súčet cien vybraných hrán. Problém Min-Cut vyžaduje nájsť s − t
rez minimálnej ceny.
Klasický výsedok teórie grafov hovorí, že pre dané G, s, t, e sa veľkosť maximálneho s−t toku rovná veľkosti minimálneho s−t rezu. Jeden z pohľadov na túto vetu
je pomocou duality lineárneho programu. Nech Ps,t označuje množinu všetkých s−t
ciest v G. Uvažujme lineárny program
P
max
xπ
(7.1)
π∈Ps,t
za predpokladu
∀e ∈ E :
P
x π ≤ ce
π:e∈π
∀π ∈ Ps,t : xπ ≥ 0
Program (7.1) má premennú pre každú s − t cestu v G, pričom pre každú hranu
platí, že súčet premenných všetkých ciest, ktoré cez ňu prechádzajú, je menší ako jej
kapacita. Každé prípustné riešenie preto generuje tok: pre hranu e = (u, v) zoberme
všetky s − t cesty, ktoré ňou prechádzajú; ich príspevok rozdeľme do f (u, v) a
f (v, u) podľa smeru. Naopak, každému toku zodpovedá prípustné riešenie (7.1),
69
Min-Cut
70
KAPITOLA 7. TOKY A REZY
ako sa dá ľahko ukázať indukciou na počet dvojíc u, v s nenulovou hodnotou toku1 .
Vyriešenie programu (7.1) preto znamená nájdenie maximálneho toku2 . Zostrojme
teraz syntaktickými manipuláciami duálny program:
P
min
e∈E
za predpokladu
∀π ∈ Ps,t :
ye ce
P
(7.2)
ye ≥ 1
e:e∈π
∀e ∈ E : ye ≥ 0
Multiway-Cut
A
7.1
FT
Program (7.2) má premennú ye pre každú hranu e ∈ E, pričom vyžadujeme, aby
na každej s − t ceste bol súče hadnôt premenných aspoň 1. Pri pozornejšom pohľade
zistíme, že keby ye ∈ {0, 1} reprezentovalo, či je daná hrana vybratá, dostali by sme
celočíselný program pre Min-Cut. Program (7.2) je preto racionálnou relaxáciou
pre Min-Cut a spomínaný klasický výsledok hovorí, že optimálne riešenie programu
(7.2) je celočíselné.
V tejto časti budeme študovať niekoľko variant problému minimálneho rezu, pre
ktoré je síce možné formulovať lineárne programy s podobnou interpretáciou (tok
vs. rez), ale nemajú spomínanú vlastnosť celočíselnoti optimálneho riešenia.
Uvažujme najprv nasledujúce zovšeobecnenie problému minimálneho rezu:
MinMultiway-Cut
Definícia 7.3 Majme daný graf G = (V, E), v ňom množinu terminálnych vrcholov
S = {s1 , . . . , sk } ⊆ V a funkciu c : E 7→ Q+ udávajúcu cenu hrán. Problém MinCut vyžaduje nájsť hranový rez minimálnej ceny taký, že žiadna dvojica vrcholov
si , sj nie je v rovnakej komponente súvislosti.
D
R
Zrejme pre k = 2 dostávame Min-Cut problém. Pre k ≥ 3 je však rozhodovacia
verzia probému NP-úplná. Za povšimnutie stojí, že relaxovaná verzia nemusí mať
celočíselné riešenie (inak by bol problém polynomiálne riešiteľný, podobne ako MinCut), ako vidno z obrázka 7.1.
s1
s2
s3
Obr. 7.1: Relaxovaná verzia Min-Cut problému má riešenie, v ktorom všetkých 6
hrán má hodnotu 1/3, preto každá cesta medzi dvoma terminálmi má hodnotu 1
a celková hodnota riešenia je 2. Na duhej strane, každé celočíselné riešenie musí
vybrať aspoň 3 hrany.
1 Ak je tok nenulový, musí existovať s − t cesta π s nenulovými hodnotami toku. Nech q je
minimum z týcho hodnôt; odčítajme ho od všetkých hrán cesty a vyrobme príslušnú premennú
xπ = q v programe (7.1). V G nám ostane tok, v ktorom je menej nenulových dvojíc u, v (jednu
sme práve odstránili).
2 Čitateľa nech nemätie, že (7.1) je exponenciálne veľký. Maximálny tok sa dá nájsť efektívne v
polynomiálnem čase.
7.1. MULTIWAY-CUT
71
Ukážeme teraz algoritmus, ktorý má aproximačný pomer 2 1 − k1 . Pre každý
vrchol si označme Ci minimálny rez, ktorý oddelí si od všetkých ostatných terminálov. Ci sa dá jednoducho vypočítať tak, že vrcholy S − {si } stotožníme do jedného
vrchola a v takto upravenom grafe nájdeme minimálny rez.
Algoritmus 15 Min-Mulitway-Cut
1: pre každé i = 1, . . . , k vypočítaj Ci
2: výsledný rez je zjednotenie hrán z k − 1 najlacnejších rezov Ci
FT
Aproximačný pomer sa dá ukázať nasledovne. Uvažujme optimálne riešenie A
s hodnotou m? , t.j. najlacnejší rez, ktorý oddelí všetky dvojice terminálov. Zrejme
G po odstránení tohto rezu pozostáva z k komponentov súvislosti, pričom každý
terminál je v jednom komponente (menej komponentov nemôže byť, lebo by dva
terminály museli byť v jednom komponente; viac nemôže byť z minimality rezu).
Pre i-ty komponent označme Ai jeho hranovú hranicu (t.j. hrany, ktoré majú jeden
koniec v ňom a jeden mimo neho). Ai je rez, ktorý oddeľuje i-ty komponent od
zvyšku grafu, a teda oddeľuje si od ostatných terminálov. Keďže Ci je minimálny
rez, ktorý oddeľuje si od ostatných terminálov, musí platiť
w(Ai ) ≥ w(Ci )
Zároveň ale platí
w(Ai ) = 2m?
A
k
X
i=1
pretože v ľavej sume je každá hrana rezu započítaná práve dvakrát. B.u.n.v nech
Ck je najťažší z rezov C1 , . . . , Ck . Pre cenu riešenia algoritmu platí
m=
k−1
X
w(Ci ) ≤
X
k
w(Ci ) ≤
i=1
R
i=1
1
1−
k
1
1−
k
X
k
1
w(Ai ) = 2 1 −
m?
k
i=1
pričom prvá nerovnosť vyplýva z toho, že pre najťažší rez Ck platí
D
w(Ck ) ≥
k
1X
w(Ci )
k i=1
s1
2−ε
s2
1
2−ε
s4
2−ε
1
1
1
2−ε
s3
Obr. 7.2: Tesný odhad pre algoritmus 15 pre k = 4. Každý z rezov Ci má cenu 2 − ε,
takže celé riešenie algoritmu má cenu 6 − 3ε = (k − 1)(2 − ε). Optimálne riešenie
má hodnotu k = 4.
72
KAPITOLA 7. TOKY A REZY
7.2
Min-k-Cut
V tejto časti uvažujme iné zovšeobecnenie problému minimálneho rezu. V tomto
prípade je cieľom pre dané k nájsť minimálny rez, ktorý rozdelí graf G na k komponentov súvislosti (na rozdiel od predchádzajúceho problému, v tomto prípade nezáleží na tom, ktoré vrcholy ktorý komponent
obsahuje). Opäť nájdeme algoritmus,
ktorý má aproximačný pomer 2 1 − k1 . Algoritmus je založený na tzv. Gomory-Hu
stromoch, ktoré efektívne kódujú minimálne rezy medzi každou dvojicou vrcholov.
Gomory-Hu stromy
Definícia 7.4 Majme daný graf G = (V, E) s ohodnotením hrán c : E 7→ R+ .
Označme f (u, v) veľkosť minimálneho u−v rezu v G. Gomory-Hu strom je strom T s
množinou vrcholov V (pričom hrany T nijak nesúvisia s hranami G) s nasledovnými
vlastnosťami.
FT
Gomory-Hu
strom
1. Hrany T sú ohodnotené funkciou c0 : ET 7→ R+ , pričom c0 (u, v) je definovaná
nasledovne: hrana (u, v) rozdelí strom na dve komponenty súvislosti, a teda
rozdelí vrcholy V na dve množiny A, A; nech cut(u, v) je cena hranového rezu
v grafe G medzi A, A. Potom c0 (u, v) = cut(u, v).
A
2. Pre každé dva vrcholy u, v je cena minimálneho u − v rezu v T (t.j. cena
najlacnejčej hrany na jedinej u − v ceste v T ) rovná f (u, v).
b
2
10
2
R
8
b
18
d
e
e
f
17
5
7
3
f
a
4
2
3
a
D
c
4
13
c
15
14
d
Obr. 7.3: Graf a jeho Gomory-Hu strom.
Uvedieme teraz algoritmus, ktorý k danému n-vrcholovému grafu nájde GomoryHu strom s použitím n − 1 výpočtov minimálneho rezu. Algoritmus si udržiava partíciu vrcholov V , {S1 , . . . , St }. Začína s jednoprvkovou partíciou S1 = V , pokračuje
n − 1 iteráciami, pri ktorých postupne partíciu zjemňuje, až skončí s n-prvkovou
partíciou S1 , . . . , Sn , kde každé Si je jednoprvková množina. Algoritmus si udržuje
strom T , ktorého vrcholy sú S1 , . . . , St a hrana (Si , Sj ) ∈ ET má cenu c0 (Si , Sj ); po
skončení algoritmu bude strom T hľadaný Gomory-Hu strom.
Počas behu algoritmu platí nasledovný invariant:
7.2. MIN-K-CUT
73
Invariant Pre každú hranu (Si , Sj ) ∈ ET existujú dva vrcholy a ∈ Si , b ∈ Sj tak,
že c0 (Si , Sj ) = f (a, b) a zároveň rez definovaný hranou (Si , Sj ) je minimálny a − b
rez v G.
FT
Algoritmus 16 Gomory-Hu strom
1: S1 := V
2: for t = 2 to n do
3:
nech Si obsahuje aspoň dva vrcholy x, y.
4:
zakoreň T v Si
5:
nech Sk1 , . . . , Skr sú synovia Si v T a Tk1 , . . . , Tkr sú príslušné podstromy
6:
nech Vkj sú tie vrcholy grafu G, ktoré sa nachádzajú v niektorom Sl ∈ Tkj
7:
vyrob graf G0 tak, že v grafe G sa stotožnia vrcholy Vki do jedného vrchola
vki pre všetky i
8:
nájdi minimálny x − y rez v G0 ; nech má cenu w
9:
rozdeľ Si na Six a Siy podľa nájdeného rezu
10:
pridaj do T hranu (Six , Siy ) s cenou w
11:
vrcholy Ski vhodne napoj na Six alebo Siy
12: end for
R
A
Potrebujeme dokázať dve veci: jednak, že invariant ostáva počas behu algoritmu
zachovaný a dvak, že po skončení algoritmu je výsledkom Gomory-Hu strom.
Pozrime sa na situáciu po skončení algoritmu. Keďže všetky množiny Si sú jednoprvkové, máme ohodnotený strom na množine vrcholov V . Overíme, že platia
obidve podmienky z definíce Gomory-Hu stromu. Prvá podmienka hovorí, že ohodnotenie hrany stromu c0 (u, v) = cut(u, v), t.j. cena rezu (v grafe G) definovaného
(stromovou) hranou u − v. Z platnosti invariantu vyplýva, že príslušný rez je minimálny u − v rez a ohodnotenie hrany je jeho veľkosť (f (u, v)).
Druhá podmienka vyžaduje, aby cena minimálneho rezu medzi ľubovoľnými
dvoma vrcholmi bola rovnaká v grafe aj v jeho Gomory-Hu strome. Z platnosti invariantu vyplýva, že pre každú hranu (u, v) výsledného stromu platí c0 (u, v) = f (u, v),
t.j. cena minimálneho u − v rezu v G. Uvažujme teraz dva vrcholy u, v, ktoré nie sú
spojené hranou v strome. Nech emin = (u0 , v 0 ) je minimálna hrana na u − v ceste
v T . Hrane emin zodpovedá rez v G, ktorý oddelí vrcholy u0 a v 0 (a teda aj u a v)
a c0 (u0 , v 0 ) je cena tohoto rezu. To ale znamená, že c0 (u0 , v 0 ) je cena nejakého u − v
rezu v G, preto c0 (u0 , v 0 ) ≥ f (u, v). Aby sme ukázali aj opačnú nerovnosť, t.j. že
c0 (u0 , v 0 ) ≤ f (u, v), dokážeme najprv nasledujúcu lemu:
D
Lema 7.1 Nech f (u, v) označuje veľkosť minimálneho u − v rezu v grafe G. Pre
každú cestu v1 , v2 , . . . , vk platí
f (v1 , vk ) ≥ min{f (v1 , v2 ), f (v2 , v3 ), . . . , f (vk−1 , vk )}
Dôkaz: Uvažujme ľubovoľné tri vrcholy u, v, w a nech f (u, v) ≤ f (u, w) ≤ f (v, w).
Potom musí platiť f (u, v) = f (u, w): uvažujme minimálny u − v rez, ktorý rozdelí
vrcholy grafu na množiny V1 a V2 tak, že u ∈ V1 a v ∈ V2 . Ak w ∈ V2 , potom máme
u − w rez s cenou f (u, v) a teda f (u, v) = f (u, w); ak w ∈ V1 , potom máme v − w
rez a f (v, w) = f (u, w) = f (u, v).
Pre ľubovoľné vrcholy u, v, w preto platí f (u, v) ≥ min{f (u, w), f (v, w)}. Dôkaz
dokončíme indukciou na dĺžku cesty.
Teraz môžme dokázať, že c0 (u0 , v 0 ) ≤ f (u, v) nasledovne: nech spomínaná u − v
cesta má vrcholy u, w1 , w2 , . . . , wk , v. Potom platí
f (u, v) ≥ min{f (u, w1 ), f (w1 , w2 ), . . . , f (wk , v)} = min{c0 (u, w1 ), c0 (w1 , w2 ), . . . , c0 (wk , v)}
Minimum na pravej strane sa nadobúda práve pre c0 (u0 , v 0 ) = emin .
74
KAPITOLA 7. TOKY A REZY
FT
Dokázali sme, že ak po skončení algoritmu platí invariant, výsledkom je GomoryHu strom. Dôkaz korektnosti algoritmu zakončíme tým, že ukážeme, že invariant
ostáva v platnosti počas celého behu algoritmu, t.j. že ak iterácia algoritmu začne
v situácii, v ktorej platí invariant, tak invariant platí aj po skončení iterácie.
Uvažujme situáciu na začiatku iterácie algoritmu, v ktorej platí invariant. Iterácia pridá hranu (Six , Siy ) a zmení hrany (Skj , Si ) na (Skj , Six ) alebo (Skj , Siy ). Všetky
ostatné hrany ostávajú nezmenené, preto aj invariant na nich platí. Spresnime riadok 11 algoritmu nasledovne: nech (Skj , Si ) je pôvodná hrana a nech a ∈ Skj , b ∈ Si
sú vrcholy z definície invariantu. Ak a ∈ Six , potom sa vrchol Skj pripojí k Six , inak
k Siy . Takto ostane platnosť invariantu zachovaná aj pre hrany incidentné s Skj .
Ostáva ukázať platnosť invariantu pre hranu (Six , Siy ). Cena hrany (Six , Siy ) je cena
minimálneho x − y rezu v grafe G0 a navyše rez definovaný hranou (Six , Siy ) je minimálny rez G0 . Ostáva nám teda ukázať, že minimalita rezu sa prenáša z G0 do G,
čo vyplýva z nasledujúcej lemy:
Lema 7.2 Uvažujme graf G = (V, E) a v ňom minimlny x − z rez A, A tak, že
z ∈ A. Zostrojme (multi)graf G0 z G stotožnením vrcholov množiny A. Nech W, W
je minimálny x − y rez v G0 . Potom W, W je aj minimálny x − y rez v G.
S
S
y
A
x
A
z
Obr. 7.4: Ilustrácia Lemy 7.2
R
Dôkaz: Uvažujme minimálny x − y rez v G, nech je to S, S. Ak A ⊆ S alebo
A ⊆ S, tomuto rezu priamočiaro zodpovedá rez v G0 . Predpokladajme teda za
účelom sporu, že v G existuje minimálny x − y rez tak, že množina A je rozdelená
medzi S a S. Potom ale z minimality S, S rezu vyplýva, že A ∩ S je menší x − z rez
– spor.
D
Vráťme sa teraz k problému Min-k-Cut.
Veta 7.3 Algoritmus 17 je 2 1 − k1 -aproximačný algoritmus pre problém Min-kCut.
Algoritmus 17 Min-k-Cut
1: vypočítaj Gomory-Hu strom T pre daný graf.
2: vyber k − 1 najlacnejších hrán stromu T ; nech k i-tej hrane zodpovedá rez Ci
v grafe G
3: výsledok je zjednotenie rezov Ci
Dôkaz: Ľahko vidno, že algoritmus 17 vráti korektný k-rez. Ideme ukázať aproximačný pomer. Nech optimálne riešenie rozdelí graf G na komponenty C1 , . . . , Ck ;
nech Ai je veľkosť hranovej hranice Ci (t.j. súčet váh hrán, kotré majú jeden koniec
v Ci a hruhý mimo Ci ) a platí A1 ≤ A2 ≤ · · · Ak . Zrejme
2m∗ =
k
X
i=1
Ai
7.3. MIN-MULTICUT
75
7.3
FT
Z Gomory-Hu stromu T zostrojme graf T 0 tak, že skontrahujeme každý komponent
Ci do jedného vrchola, takže dostaneme graf s k vrcholmi; ak v strome T bola hrana
medzi vrcholmi z Ci a Cj , v T 0 bude hrana medzi príslušnými vrcholmi. Odstráňme
z T 0 hrany tak, aby ostal strom T 00 s k vrcholmi. Každá hrana stromu T 00 definuje
rez v G podľa Gomory-Hu stromu T . Ukážeme, že k − 1 hrán stromu T 00 možno
zoradiť tak, že cena rezu prislúchajúceho i-tej hrane bude nanajvýš Ai . Z toho
potom vyplynie, že v T existuje k − 1 hrán, ktoré sú v poradí lacnejšie ako k − 1
najlacnejších (čo do veľkosti hranovej hranice) komponentov optimálneho riešenia.
Zakoreňme strom T 00 vo vrchole Ck (t.j. vrchole s najväčšou hranovou hranicou). Hrany T 00 takto získajú orientáciu od otca k synom. Každej hrane môžme
jednoznačne priradiť vrchol, do ktorého smeruje. Nech hrana e = (Ci , Cj ) má priradený vrchol Cj . Hrana e pochádza z Gomory-Hu stromu ako hrana medzi dvoma
vrcholmi u ∈ Ci a v ∈ Cj , pričom váha hrany e je cena minimálneho u − v rezu.
Lenže hranová hranica Ci tiež oddeľuje vrcholy u a v (t.j. tvorí nejaký u − v rez) a
preto cena e je nanajvýš Aj .
Min-Multicut
Prv, než pokročíme v úvahách, uveďme ešte jeden lineárny program opisujúci problém minimáneho rezu:
P
ye ce
(7.3)
A
min
e∈E
za predpokladu
∀e = (u, v) ∈ E : ye ≥ pu − pv
ps − pt ≥ 1
∀e ∈ E : ye ≥ 0
∀v ∈ V : pv ≥ 0
D
R
Program (7.3) má, na rozdiel od programu (7.2) polynomiálnu veľkosť. Navyše
ľahko vidno, že oba programy sú ekvivalentné: v programe (7.3) má každý vrchol
nezáporný “potenciál” pv , pričom hodnota premennej ye je aspoň rozdiel potenciálov koncových vrcholov. Ak si zoberieme riešenie (7.2), pričom ye interpretujeme
ako dĺžku hrany e a priradíme každému vrcholu v hodnotu pv rovnajúcu sa jeho
vzdialenosti (meranej pomocou ye ) od s, dostaneme riešenie (7.3). Naopak, ak máme
riešenie (7.3) potom na každej s − t ceste je súčet rozdielov potenciálov aspoň 1.
Program (7.3) je teda (polynomiálne veľký) lineárny program pre problém MinCut.
V ďalšej časti sa budeme zaoberať zovšeobecnením problému Max-Flow na
viacero komodít. Predpokladajme, že v grafe G máme daných k dvojíc si , ti a
chceme nájsť pre každú z nich tok tak, aby všetky toky zdieľali kapacity hrán.
Cieľom je maximalizovať súčet tokov:
max
k
P
P
xπ i
(7.4)
i=1 π i ∈Psi ,ti
za predpokladu
P
∀e ∈ E :
x π j ≤ ce
π j :e∈π j
∀i∀π ∈ Psi ,ti : xπi ≥ 0
Duálny program bude:
min
P
e∈E
ye ce
(7.5)
76
KAPITOLA 7. TOKY A REZY
za predpokladu
∀i∀π i ∈ Psi ,ti :
P
ye ≥ 1
e:e∈π i
∀e ∈ E : ye ≥ 0
Duálne premenné opäť zodpovedajú hranám, pričom vyžadujeme, aby pre každú
dvojicu si , ti platilo, že súčet duálnych premenných na hranách cesty je aspoň 1.
Podobne ako v predchádzajúcich úvahách, môžme program (7.5) interpretovať ako
relaxovanú verziu problému Min-Multi-Cut, pri ktorom je cieľom vybrať minimálny hranový rez, ktorý oddelí všetky dvojice si , ti :
Definícia 7.5 Daný je graf G = (V, E) s ohodnotením hrán e : E 7→ Q+ a dvojice
vrcholov si , ti pre i = 1, . . . , k. Cieľom je nájsť množinu hrán E 0 ⊆ E tak, aby pre
každé i = 1, . . . , k platilo, že si a ti sú v rôznych komponentoch grafu G − E 0 .
FT
Min-MultiCut
Prirodzená otázka je, či sa dá rovnakým spôsobom zovšeobecniť aj max-flowmin-cut veta, t.j. či platí, že maximálny multikomoditný tok sa rovná minimálnemu
multirezu (inými slovami, či program (7.5) má celočíselné optimálne riešenie). Odpoveď je síce záporná, ale ukážeme slabšie tvrdenie:
A
Veta 7.4 Majme daný graf G = (V, E) s ohodnotením hrán e : E 7→ Q+ a dvojice
vrcholov si , ti pre i = 1, . . . , k. Nech m∗f low je hodnota optimálneho riešenia pre
problém multikomoditného toku a m∗cut je veľkosť minimálneho separujúceho rezu.
Potom platí
m∗f low ≤ m∗cut ≤ 4 ln(2k)m∗f low
D
R
Dôkaz: Nech m∗Qcut je veľkosť minimálneho hranového multirezu. Ľavá nerovnosť
je triviálna, pretože m∗f low = m∗Qcut a m∗Qcut ≤ m∗cut .
Uvažujme program (7.5), čo je lineárny program, ktorého riešením je m∗Qcut , čiže
aj m∗f low . Analogicky ako sme z programu (7.2) dostali program (7.3), môžme aj
program (7.5) prepísať tak, aby mal polynomiálnu veľkosť, a teda bol riešiteľný v
polynomiálnom čase. Na to, aby sme dokázali tvrdenie vety, nájdeme algoritmus,
ktorý vezme optimálny relaxovaný multirez (t.j. optimálne riešenie programu (7.5))
a vyrobí z neho rez s cenou max. 4 ln(2k)-krát väčšou.
Riešenie relaxovaného multirezu tvoria premenné ye pre každú hranu e = (u, v).
Označme d(u, v) = ye∗ , kde y ∗ je optimálne riešenie. Hodnotu d(u, v) budeme interpretovať ako dĺžku hrany; tieto dĺžky definujú prirodzeným spôsobom vzdialenosť
δ(u, v) medzi ľubovoľnými dvoma vrcholmi. Z prípustnosti riešenia vieme, že pre
každú dvojicu si , ti je δ(si , ti ) ≥ 1. Ak kapacity hrany ce budeme interpretovať
ako prierez, potom optimálne riešenie relaxovaného multirezu minimalizuje celkový
objem hrán, t.j.
X
Ψ=
ce d(u, v)
e=(u,v)∈E
Náš algoritmus vyrobí postupnosť dizjunktných množín vrcholov V1 , V2 , . . . , Vh pre
h ≤ k tak, že pre každú množinu Vr platí
1. ∀i = 1, . . . , k : si 6∈ Vr ∨ ti 6∈ Vr
2. ∃l : sl ∈ Vr ∨ tl ∈ Vr
Splnenie týchto dvoch vlastností nám zaručí, že rez, definovaný množinami V1 , V2 , . . . , Vh
separuje každú z dvojíc si , ti .
Ako budeme vyberať množiny Vr ? Označme G0r = (Vr0 , Er0 ) graf, ktorý vznikne
po odstránení množín V1 , . . . , Vr−1 z grafu G. Ak G0r neobsahuje žiadnu dvojicu
si , ti , algoritmus skončí. Inak vyberie dvojicu {si , ti } ⊆ Vr0 a nájde množinu Vr
7.3. MIN-MULTICUT
77
tak, aby si ∈ Vr a ti 6∈ Vr . Prirodzeným spôsobom si zadefinujeme pojem gule s
polomerom ρ:
Bρ (v) = {u ∈ Vr0 | δ(u, v) ≤ ρ}
Množina Vr bude guľa vhodného polomeru ρ okolo vrchola si . Ostáva nám určiť
ako vybrať ρ. V prvom rade chceme, aby ρ < 1/2, čo nám zaručí, že žiadna dvojica nebude ležať vo Vr (vzdialenosť každej dvojice je aspoň 1). Ďalej si zavedieme
niekoľko pojmov. Vnútorné hrany gule sú
Eρ (v) = {(w, z) ∈ Er0 | w, z ∈ Bρ (v)}
FT
Hranová hranica gule je
E ρ (v) = {(w, z) ∈ Er0 − Eρ (v) | w ∈ Bρ (v) ∨ z ∈ Bρ (v)}
Objem gule definujeme mierne neštandardne tak, že okrem objemu hrán pridáme z
technických dôvodov člen Ψ/k:
Vρ (v) =
Ψ
+
k
X
X
c(w, z)d(w, z) +
(w,z)∈Eρ (v)
c(w, z) (ρ − min(δ(v, w), δ(v, z)))
(w,z)∈E ρ (v)
A
Vnútorné hrany gule prispievajú do jej objemu celým svojím objemom, hrany z
hranovej hranice iba príslušnou časťou. Najviac nás, pochopiteľne, zaujíma cena
gule, t.j. veľkosť jej hranového rezu:
X
Cρ (v) =
c(w, z)
(w,z)∈E ρ (v)
Konečne sa dostávame k tomu, ako zvoliť polomer ρ v množine Vr . Chceme, aby
guľa, ktorú odseparujeme mala čo najmenšiu jednotkovú cenu, t.j.
Cρ (v)
Vρ (v)
R
Fρ (v) =
D
Funkcia F : ρ 7→ Fρ (v) pre daný vrchol v má body nespojitosti pre tie hodnoty
ρ, pre ktoré existuje vrchol w vo vzdialenosti ρ od v. Na každom intervale medzi
bodmi nespojitosti je F diferencovateľná a klesajúca.
*** to do: obrázok ***
Preto môžme ľahko nájsť minimum Fρ (si ) na intervale (0, 1/2): vyberieme minimum z hodnôt Fρ (si ) pre ρ = δ(si , u) − ε.
Ostáva nám ukázať, že takto získaný rez je naozaj dobrou aproximáciou. Na to
ukážeme nasledovné tvrdenie:
∀v∃ρ < 1/2 : Fρ (v) ≤ 2 ln(2k)
(7.6)
Z neho potom vyplynie požadovaná aproximácia: nech algoritmus vyberie gule
Bρ1 (si1 ), . . . , Bρh (sih ). Cena rezu je
m=
h
X
j=1
C(sij , ρj ) ≤ 2 ln(2k)
h
X
V (sij , ρj )
j=1
V poslednej sume sa členy Ψ/k z definície objemu zosumujú najviac do Ψ a zvyšné
objemy opäť najviac do Ψ, a teda m ≤ 2 ln(2k)2Ψ.
Dôkaz dokončíme dôkazom tvrdenia (7.6): Fixujme si vrchol v a uvažujme všetky
funkcie ako funckie vzdialenosti ρ. Ak V (ρ) je diferencovateľná, platí V 0 (ρ) = C(ρ).
Preto
V 0 (ρ)
0
= [ln V (ρ)]
F (ρ) =
V (ρ)
78
KAPITOLA 7. TOKY A REZY
Tvrdenie (7.6) dokážeme sporom: predpokladajme, že pre všetky ρ < 1/2 platí
F (ρ) > 2 ln(2k). Ak F je diferencovateľná na intervale (0, 1/2), máme
0
[ln V (ρ)] > 2 ln(2k)
obe strany zintegrujeme určitým integrálom od 0 po 1/2 a dostaneme
V 21
ln
> ln 2k
V (0)
a odtiaľ
1
> 2kV (0) = 2Ψ
2
FT
V
čo je spor, lebo V (ρ) ≤ Ψ + Ψ/k Ak F nie je diferencovateľná na intervale (0, 1/2),
zopakujeme predchádzajúcu úvahy na každom inetrvale spojitosti a výsledky sčítame.
7.4
A
Ukázali sme, ako aproximovať problém multirezu s aproximačným pomerom
log(k). Teraz sa zamerajme na špeciálny prípad, keď graf G bude strom. Aj keď sa
na prvý pohľad tento problém javí ako jednoduchý (v strome existuje práve jedna
cestamedzi každou dvojicou si , ti ), v skutočnosti je NP-úplný už aj v prípade, ak
všetky rany majú rovnakú váhu a strom má hĺbku 13 .
*** to do: multicut na stromoch ***
Max-Cut
Definícia 7.6 Majme daný graf s ohodnotenými hranami, t.j. množinu vrcholov V
+
a funkciu w : V 2 7→ R
P . Cieľom je nájsť množinu vrcholov S ⊆ V tak, aby príslušný
indukovaný rez (t.j. i∈S,j∈V −S wij ) bol maximálny.
*** to do: 2-aproximačný greedy algoritmus ***
Skúsme zapísať problém maximálneho rezu ako matematický program: majme
pre každý vrchol vi premennú yi ∈ {−1, 1}. Premenné yi určujú rez tak, že vrcholy s
hodnotou 1 sú na jednej strane rezu a vrcholy s hodnotou -1 na druhej.
Výraz yi yj je
P
1, ak sú vrcholy i, j v jednej časti rezu a -1 inak. Preto výraz 21 i,j∈V wij (1 − yi yj )
udáva veľkosť rezu. Aby sme vynútili yi ∈ {−1, 1}, stačí vyžadovať yi2 = 1, yi ∈ {R}.
Dostali sme tzv. striktne kvadratický4 program
D
Max-Cut
R
Videli sme, že problém Min-Cut je efektívne riešiteľný, hoci jeho modifikácie pre
viacero rozrezávaných vrcholov už nie sú. Pozrime sa teraz na opačný problém
hľadania maximálneho rezu. Neprekvapí, že, podobne ako pri hľadaní najkratšej a
najdlhšej cesty, je hľadanie maximálneho rezu ťažký problém.
max
1 X
wij (1 − yi yj )
2
(7.7)
i,j∈V
yi2 = 1, yi ∈ R
3 Uvažujme nasledovnú redukciu z problému minimálneho vrcholového pokrytia: majme daný
graf G, v ktorom treba nájsť minimálnu množinu vrcholov tak, aby každá hrana bola incidentná
aspoň s jedným vybraným vrcholom. Zostrojme strom T tak, že vrcholy grafu G budú listy a
všetky listy budú napojené na koreň stromu. Zostrojme inštanciu multirezu tak, že pre každú
hranu (u, v) z G pridáme dvojicu si = u, ti = v. Uvažujme ľubovoľné riešenie multirezu v T a
zostrojme z neho pokrytie v G tak, že vyberieme tie listy, z ktorých hrana do koreňa stromu je
vybratá v multireze. Ľahko vidno, že sme dostali vrcholové pokrytie.
4 striktne kvadratický program je taký, kde sa každá premenná v účelovej funkcii aj v ohraničenia
vyskytuje v súčine stupňa 2
7.4. MAX-CUT
79
Podobne ako pri riešení celočíselných lineárnych programov sme riešili relaxáciu do
reálnych čísel, pri striktne kvadratických programoch je štandardným postupom relaxácia do viacerých rozmerov: na čísla ±1 sa pozrieme ako na jednotkové vektory v
jednorozmernom priestore a nahradíme ich jednotkovými vektormi v n-rozmernom
priestore, pričom súčin čísel nahradíme skalárnym súčinom. Dostaneme tak vektorový program
max
1 X
wij (1 − hvi , vj i)
2
(7.8)
i,j∈V
FT
hvi .vi i = 1, vi ∈ Rn
D
R
A
Všimnime si, že keď zoberieme riešenie programu (7.7) a premennú yi nahradíme
vektorom (yi , 0, 0, . . . , 0), dostaneme riešenie programu (7.8). Program (7.8) je preto
relaxáciou programu (7.7). Otázka znie, či sme si touto redukciou pomohli: v pôvodnom zadaní sme mali n premenných s kvadratickými obmedzeniami, teraz máme
n2 premenných a tiež s kvadratickými obmedzeniami. Kupodivu, ako hneď uvidíme, vektorové programy sa dajú riešiť s ľubovoľnou presnosťou. Na to, aby sme
to ukázali,
KAPITOLA 7. TOKY A REZY
D
R
A
FT
80
Kapitola 8
Táto kapilola je zatiaľ iba plánovaná
FT
Stromy a kostry
Metric Steiner tree
8.0.2
Steiner tree
8.0.3
Steiner forest
8.0.4
Steiner network
8.0.5
Constrained MST via matroid intersection
D
R
A
8.0.1
81
KAPITOLA 8. STROMY A KOSTRY
D
R
A
FT
82
D
R
A
[1] TODO
FT
Literatúra
83
Download

draft - Kedrigern