Approxim´ aci´ os algoritmusok el˝ oad´ as jegyzet 2012. tavaszi f´el´ev El˝oad´o: Kis Tam´ as Lejegyezt´ek: ´ Csaba Akos Dud´ as L´ aszl´ o Fodor P´ eter Hetei Bal´ azs Horv´ ath Vanda Majoros Csilla Retek D´ avid Szajk´ o Anik´ o ELTE, Budapest, 2012. m´ajus 31.
1. 1.1.
El˝ oad´ as, 2012.02.17. Le´ırta: Retek D´ avid Bevezet˝ o
Sok gyakorlati probl´ema vezet egy NP neh´ez feladathoz. Ilyen probl´em´ak eset´en ker¨ ul el˝ot´erbe, hogy ha m´ar nem tudjuk ”gyorsan” megkeresni a pontos megold´ast, legal´abb valamilyen k¨ozel´ıt˝o megold´ast pr´ob´aljunk meg adni. Ekkor viszont az algoritmushoz tartoznia kell egy garanci´anak is, hogy a (k¨ozel´ıt˝o) eredm´eny¨ unk legfeljebb mennyire t´er el az optim´alis megold´ast´ol. A k´es˝obbiekben az I inputra vett (elm´eleti/abszol´ ut) optim´alis megold´as ´ert´ek´et OPT-tal, az algoritmusunk a´ltal adott ´ert´eket A(I)-vel jel¨olj¨ uk.
1.2.
Alapfogalmak
Defin´ıci´ o: Approxim´aci´os algoritmus minimaliz´al´asi feladatra Fix ε > 0 eset´en A algoritmus (1 + ε) approxim´aci´o, ha minden I inputra A(I) ≤ OPT(I)(1 + ε). Ekkor (1 + ε) az approxim´aci´os garancia/h´anyados. A fenti esetben az algoritmus j´os´ag´at a legrosszabb inputra adott teljes´ıtm´enye szerint hat´arozzuk meg.
1.3.
S´ ulyozott cs´ ucsfed´ esi probl´ ema
Feladat: Adott G = (V, E) gr´af ´es c : V → R+ s´ ulyf¨ uggv´eny eset´en keress¨ uk azon U ⊆ V cs´ ucshalmazt, melyre teljes¨ ul, hogy (a) Az U -beli cs´ ucsok lefogj´ak az ¨osszes ´elt, P (b) c(U ) = u∈U c(u) a lehet˝o legkisebb. A feladat a´ltal´anos gr´afokra NP neh´ez, ´ıgy indokol approxim´aci´os algoritmust keresni r´a. 1.3.1.
Spec. eset (c ≡ 1)
Ekkor a feladat, minim´alis m´eret˝ u lefog´o cs´ ucshalmaz keres´ese. Als´ o korl´ at az optimumra: Minden M p´aros´ıt´asra G-ben teljes¨ ul, hogy |M | ≤ OPT. Ugyanis ahhoz, hogy az M p´aros´ıt´asban szerepl˝o ´eleket lefogjuk, az M -beli ´elnek legal´abb egyik v´egpontj´at tartalmaznia kell a lefog´o halmaznak. Fels˝ o korl´ at az optimumra: Legyen M maxim´alis p´aros´ıt´as G-ben, ekkor 2|M | ≥ OPT. 1
Ugyanis indirekt tegy¨ uk fel, hogy V (M ) (vagyis az M beli ´elek v´egpontjai) nem fognak le minden ´elt. Ekkor legal´abb egy ilyen ´ellel n¨ovelhetn´enk az M p´aros´ıt´asunkat, ami ellentmond M maximalit´as´anak. Algoritmus: (a) Keress¨ unk maxim´alis p´aros´ıt´asa G-ben, legyen ez M . (b) U := V (M ) T´ etel: A fenti algoritmus 2 approxim´aci´o. Bizony´ıt´ as: Tetsz˝oleges M p´aros´ıt´asra G-ben, |M | ≤ OPT ≤ 2|M |.
Megjegyz´ es: A legrosszabb esetre p´elda a Kn,n teljes p´aros gr´af. M´ıg az algoritmus erre 2n pontot ad, az optim´alis m´eret˝ u megold´as n pontot tartalmaz. 1.3.2.
´ Altal´ anos eset (c ≥ 0)
Defin´ıci´ o: fok-s´ uly f¨ uggv´eny c : V → R fok-s´ uly f¨ uggv´eny, ha ∃λ ≥ 0, hogy c(v) = λ deg(v)
∀v ∈ V -re.
Lemma: Ha c fok-s´ uly f¨ uggv´eny, akkor c(V ) ≤ 2OPT. Bizony´ıt´ as: LegyenP U optim´alis lefog´o ponthalmaz G-ben (c-szerint). deg(u) ≥ |E|, mivel U lefogja az ¨osszes ´elt. Ebb˝olP k¨ovetkezik, Vegy¨ uk ´eszre,Phogy u∈U P hogy c(U ) = u∈U c(u) = u∈U λ deg(u) ≥ λ|E|. Tov´abb´a f¨olhaszn´alva, hogy v∈V deg(v) = 2|E|, ad´odik X X X λ deg(v) = λ deg(v) = 2λ|E| ≤ 2c(U ) = 2OPT. c(v) = c(V ) = v∈V
v∈V
v∈V
Defin´ıci´ o: legnagyobb fok-s´ uly f¨ uggv´eny Legyen D0 := {v ∈ V (G) : deg(v) = 0} ´es λ := minv∈V \D0 (c(v)/ deg(v)). Ekkor t(v) = λ deg(v) a legnagyobb fok-s´ uly f¨ uggv´eny. Megjegyz´ es: λ v´alaszt´asa miatt c(v) ≥ t(v) ∀v ∈ V ´es ∃v : c(v) = t(v).
2
Algoritmus(Szintez˝o algoritmus:) 1. G0 := G; c0 := c; i fut´oindex. 2. while(Gi -ben van nem 0 fok´ u cs´ ucs) i)
Legyen ti legnagyobb fok-s´ uly f¨ uggv´eny Gi -n
ii)
Di := {v ∈ V (Gi ) : deg(v) = 0}
iii)
Wi := {v ∈ V (Gi ) : ci (v) = ti (v)}
iv)
ci+1 (v) := ci (v) − ti (v) ∀v ∈ V (Gi ) \ Di
v)
Gi+1 := Gi \ (Wi ∪ Di )
3. end 4. U :=
S
Wi
T´ etel: A szintez˝o elj´ar´as 2-approxim´aci´os algoritmus a s´ ulyozott cs´ ucsfed´es probl´em´ara. Bizony´ıt´ as: Tegy¨ uk fel, hogy az algoritmus a k. l´ep´esben ´ert v´eget. Ekkor az algoritmus a´ltal adott szintez´es a k¨ovetkez˝o k´epen n´ez ki.
1. ´all´ıt´as: U lefogja az o¨sszes ´elt. S k k−1 Tekints¨ uk a gr´af V (G) = ∪k−1 ∪i=0 Di felbont´as´at. Itt minden ∪i=0 Wi -beli cs´ ucsot i=0 Wi k bevesz¨ unk, ´ıgy az ezekhez illeszked˝o o¨sszes ´elet fedi. Tov´abb´a Di v´alaszt´asa miatt, ∪i=0 Di nem fesz´ıthet ´elt. 2. ´all´ıt´as: c(U ) ≤ 2OPT Legyen C ∗ optim´alis fed´es G-n. Ekkor minden i = 1, . . . , k−1-re, a V (C ∗ ∩Gi ) cs´ ucshalmaz lefedi Gi minden ´el´et, mivel Gi gr´afot G-b˝ol cs´ ucsok elhagy´as´aval kaptuk.
3
Tov´abb´a l´atszik, hogy v ∈ U ⇒ ∃j
v ∈ Wj ⇒ c(v) =
j X
ti (v),
i=0
v ∈ V \ U ⇒ ∃j
v ∈ Dj ⇒ c(v) ≥
j−1 X
ti (v).
i=0
Ezek alapj´an, valamint a lemm´at felhaszn´alva kapjuk, hogy c(U ) =
k−1 X i=0
ti (U ∩ Gi ) ≤
k−1 X
2ti (C ∗ ∩ Gi ) ≤ 2OPT
i=0
Megjegyz´ es: A legrosszabb esetre tov´abbra is p´elda a Kn,n , c ≡ 1 s´ ulyf¨ uggv´ennyel. Itt 1 λ = n miatt t0 (v) = 1 ez´ert W0 = V (Kn,n ).
4
1
2. El˝ oad´ as, 2012. 02. 23. Le´ırta: Majoros Csilla Halmaz fed´ esi proml´ em´ ak Adott az U n elem˝ u alaphalmaz, az S = {S1 , . . . , Sk } ⊆ P(U ) halmazrendszer ´es a c : S → R+ k¨olts´egf¨ uggv´eny. Az U halmazt akarjuk lefedni az S egy r´eszhalmaz´aval, a lehet˝o legolcs´obban. Megengedett megold´asnak nevezz¨ uk a C ⊆ S halmazt, ha fed´es, azaz U ⊆ ∪S∈C S. Nyilv´anval´o, hogy ha minden u ∈ U -ra l´etezik S ∈ S, amire u ∈ S, akkor l´etezik megengedett megold´as. P Mi olyan C ⊆ S megengedett megold´ast keres¨ unk, amire a c(C) = olts´eg S∈C c(S) k¨ minim´alis. Defin´ıci´ o: Egy u ∈ U elem gyakoris´aga egyenl˝o az u elemet tartalmaz´o S ∈ S halmazok sz´am´aval. Jel¨olje f az U elemeinek maxim´alis gyakoris´ag´at. Legyen Hn = 1 + 12 · · · + n1 . K´et approxim´aci´os algoritmust fogunk megn´ezni, az els˝o a Hn szerint, a m´asodik az f szerint ad j´o megold´ast. 1. Algoritmus Defin´ıci´ o: Legyen F ⊂ U a m´ar fedett elemek halmaza. Ekkor az S halmaz hat´ekonys´aga c(S) ´ert´ek. az adott F -re n´ezve a |S\F | Az algoritmus: 1. C := ∅, F := ∅ 2. while F 6= U do 2. 1. Hat´arozzuk meg a leghat´ekonyabb halmazt azon S ∈ S-ek k¨oz¨ ul, melyekre |S \ F | ≥ 1. Legyen ezen halmaz hat´ekonys´aga α, a halmaz Sα 2. 2. Minden e ∈ S \ F -re: price(e) := α 2. 3. C := C ∪ {Sα }, F := F ∪ Sα 2. 4. end 3. az eredm´eny: C Az algoritmus elemz´ ese
2 Lemma: Tegy¨ uk fel, hogy az algoritmus az U elemeit e1 , e2 . . . en sorrendben fedi le. Ekkor OP T minden i-re price(ei ) ≤ n−i+1 . Biz. Adott i-re legyen F a m´ar fedett elemek halmaza abban az iter´aci´oban, amikor az ei pontot lefedj¨ uk. Tekints¨ unk egy optim´alis megold´ast. Az U \ F halmazt az optim´alis megold´as legfeljebb OPT k¨olts´eggel fedi (az opt megold´asunkb´ol elhagyhat´ok azok a halmazok, melyek teljesen az F -be esnek, a marad´ek m´eg mindeig lefedi U \ F -et), tekints¨ uk ezt az F r´eszfed´est. OP T ´ =: α∗ . Biz.: indirekt All.: Van olyan eleme F-nek, aminek a hat´ekonys´aga legfeljebb |U \F | t.f.h mindegyik fed´esbeli hat´ekonys´aga nagyobb α∗ -n´al. Ekkor: X X X c(S) OP T OP T OP T ≥ c(F) = c(S) = |S \ F | > |S \ F | ≥ |U \ F |, |S \ F | S∈F |U \ F | |U \ F | S∈F S∈F ellentmond´as. Az iter´aci´oban a leghat´ekonyabb halmazt v´alasztjuk, ´ıgy: price(ei ) ≤ α∗ =
OP T OP T ≤ |U \ F | n−i+1
Az els˝o egyenl˝otlens´eg az´ert igaz, mert azt az iter´aci´ot n´ezt¨ uk, ahol az ei -t lefedj¨ uk, ez´ert az ei pont a´ra megegyezik az iter´aci´oban kiv´alasztott leghat´ekonyabb halmaz hat´ekonys´ag´aval, ami az el˝oz˝o ´all´ıt´as szerint legfeljebb α∗ . Az utols´o egyenl˝otlens´eg: |F | ≤ i − 1, |U | = n ⇒ OP T OP T ≤ n−i+1 |U \ F | ≥ n − i + 1 ⇒ |U \F | T´ etel: Az algoritmus hat´ekonys´aga Hn . Biz.: Legyen az algoritmus ´altal adott megold´as C. Ekkor: c(C) =
n X
price(ei ) ≤
i=1
n X i=1
OP T = OP T · Hn n−i+1
P´ elda a legrosszab esetre: Legyen U = {1, 2, . . . , n} ´es S a´lljon az o¨sszes egyelem˝ u halmazb´ol ´es az U -b´ol. Az {i} 1 halmaz k¨olts´ege legyen n−i+1 , az U k¨olts´ege pedig 1 + . Ekkor az algorimus sorban egyenk´ent lefedi az 1, 2, . . . , n elemeket. A megold´as k¨olts´ege Hn lesz, m´ıg az OP T = 1 + . Ebb˝ol k¨ovetkezik, hogy → 0, ´es n → ∞ eset´en az algoritmus hat´ekonys´aga nem jobb, mint Hn . Az algoritmus elemz´ ese m´ ask´ epp A halmaz fed´esi feladatot modellezhetj¨ uk eg´esz´ert´ek˝ u programmal. Minden Si ∈ S halmazhoz felvesz¨ unk egy xSi bin´aris v´altoz´ot, ami 1-et vesz fel, ha az Si benne van a fed´esben, k¨ ul¨onben 0. Azt, hogy minden e ∈ U pont le legyen fedve biztos´ıtj´ak a k¨ovetkez˝o egyenl˝otlens´egek: X xSi ≥ 1, ∀e ∈ U Si :
e∈Si
3 Teh´at a feladatnak megfelel˝o eg´esz´ert´ek˝ u program a k¨ovetkez˝o: k X min{ c(Si )xSi :
IP :
i=1
X Si :
xSi ≥ 1 ∀e ∈ U,
xSi ∈ {0, 1} ∀i = 1 . . . k}
e∈Si
Ennek a line´aris programoz´asi relax´altja:
LP :
min{
k X
X
c(Si )xSi :
i=1
Si :
xSi ≥ 1 ∀e ∈ U,
xSi ≥ 0 ∀i = 1 . . . k}
e∈Si
Az LP-feladatn´al felesleges kik¨otni az xSi ≤ 1 felt´etelt, ugyanis a c k¨olts´egf¨ uggv´eny nemnegativit´asa miatt az optimum olyan megold´ason is felv´etetik, ahol minden xSi ≤ 1. Az LP-feladat du´alisa: DP :
max{
X
ye ,
e∈U
´ ıt´ All´ as. Legyen y¯ei =
price(ei ) . Hn
X
≤ c(S) ∀S ∈ S,
ye ≥ 0 ∀e ∈ U }
e∈S
Ekkor az y¯ du´al megengedett megold´as.
Biz.: K´et dolgot kell ellen˝orizni: 1) y¯ei ≥ 0 ∀ei ∈ U ;
2)
X
y¯e ≤ c(S) ∀S ∈ S
e∈S
Az 1)-es a´ll´ıt´as nyilv´anval´o. A 2)-es: Legyen S ∈ S, S = {e1 , . . . , et }. Tegy¨ uk fel, hogy az algoritmus e1 , e2 . . . , et sorrendben fedi le az S elemeit. Az i-edik S-beli elem lefed´esekor S-ben van m´eg legal´abb t − i + 1 fedetlen pont, ´ıgy az S halmaz hat´ekonys´aga legfeljebb c(S) . t−i+1 price(ei ) =”a legjobb halmaz hat´ekonys´aga az ei lefed´esekor”≤ ≤ ”az S halmaz hat´ekonys´aga” = t X i=1
y¯ei =
t X price(ei ) i=1
Hn
≤
t X i=1
c(S) t−i+1
c(S) Ht = c(S) ≤ c(S) Hn (t − i + 1) Hn
´ Ujra bel´atjuk a m´ar bizony´ıtott t´etelt: T´ etel: Az algoritmus hat´ekonys´aga Hn . Biz.: Legyen a C fed´es az algoritmus eredm´enye. Ekkor: c(C) =
n X i=1
price(ei ) =
n X i=1
Hn y¯ei = Hn
n X i=1
y¯ei ≤ Hn OP TDP = Hn OP TLP ≤ Hn OP TIP
4 Most egy m´asik algoritmust adunk a feladat megold´as´ara. Eml´ekezz¨ unk, hogy f az u ∈ U elemek maxim´alis gyakoris´aga volt. ´ ıt´ All´ as: Legyen x¯ megengedett megold´asa az LP -feladatnak. Ekkor minden e ∈ U -hoz l´etezik S ∈ S, amire e ∈ S ´es x¯S ≥ f1 P Biz.: Az LP-relax´altn´al felt˝ un˝o S:e∈S xS o¨sszegben minden e ∈ U -ra legfeljebb f tag van. Ha egy e ∈ U ponthoz tartoz´o minden x¯S < f1 volna, akkor a szumma 1-n´el kisebb volna. Algoritmus 2. 1. oldjuk meg az LP-feladatot, legyen x¯ az optim´alis megold´as 1 ha x¯S ≥ f1 ∀S ∈ S 2. xˆ = 0 k¨ ul¨onben ´ ıt´ All´ as Az algoritmusb´ol kapott xˆ megengedett megold´as. Biz.: Az el˝oz˝o a´ll´ıt´asn´al l´attuk, hogy minden e ∈ U -hoz l´etezik S ∈ S, amire e ∈ S ´es x¯S ≥ f1 . Erre az S-re xˆS = 1 lesz, ami azt jelenti, hogy e le lesz fedve az S halmazzal. ´ ıt´ All´ as Az xˆ megold´as k¨olts´ege ≤ f · OPT Biz.:
k X
c(Si ) · xˆSi ≤ f ·
i=1
k X
|i=1
c(Si ) · x¯Si ≤ f · OP T {z
=OP TLP
}
P´ elda a legrosszabb esetre: Adottak a V1 , V2 , . . . , Vf n-elem˝ u p´aronk´ent diszjunkt halmazok. Legyen U olyan hiper´elek halmaza, melyek minden Vi -b˝ol pontosan egy pontot tartalmaznak. Legyen vij0 = {a vij -re illeszked˝o hiper´elek}, ahol vij jel¨oli a Vi halmaz j-edik elem´et. Legyen S = {vij0 }. V´eg¨ ul legyen c(vij0 ) = 1 minden i, j-re. Ekkor minden e ∈ U gyakoris´aga f lesz. Az LP-feladatnak optim´alis megold´asa lesz az P nf 1 0 0 x¯vij = f vektor, a hozz´a tartoz´o optimum ´ert´eke: i,j x¯vij = f = n Az algoritmus minden ´ert´eket felkerek´ıt 1-re, ´ıgy a kapott megold´as k¨olts´ege nf lesz. 0 Az optim´alis megold´as: v´alasszuk a V1 cs´ ucsaihoz tartoz´o v1j halmazokat. ´Igy az OPT=n, az algoritmusunk f -szer rosszabb.
3. El˝ oad´ as, 2012. 03. 02. Le´ırta: Fodor P´ eter Gr´ afprobl´ em´ ak Steiner-fa probl´ ema Adott egy G = (V, E) gr´af, R ⊆ V sz¨ uks´eges cs´ ucsok halmaza, ´es egy c : E → Q + s´ ulyf¨ uggv´eny az ´eleken. A V \ R pontokat nevezz¨ uk Steiner cs´ ucsoknak. Keresend˝o F ⊆ E, amelyre: (a) F fa (k¨ormentes, o¨sszef¨ ugg˝o r´eszgr´af G-ben) (b) F fedi R o¨sszes cs´ ucs´at, ´es tetsz˝oleges cs´ ucsokat V \ R-b˝ol. (c) c(F ) a lehet˝o legkisebb. P´ elda:
Defin´ıci´ o: Metrikus Steiner-fa probl´ema (teljes gr´afon): Ugyanaz, mint a Steiner-fa probl´ema, de teljes¨ ul a h´aromsz¨og-egyenl˝otlens´eg: c(u, v) + c(v, w) ≥ c(u, w) ∀u, v, w ∈ V 1
Defin´ıci´ o: Approxim´aci´ot meg˝orz˝o redukci´o: Π1 ´es Π2 minimaliz´al´asi probl´em´ak, f ´es g algoritmusok polinomi´alis idej˝ unek Π1 ´es Π2 instanci´ainak hossz´aban. ∀I1 ∈ Π1 f (I1 ) = I2 ∈ Π2 , Az I2 minden t megold´as´ara, g(I2 , t) = s megold´asa I1 -nek.
(a) OP TΠ2 (f (I1 )) ≤ OP TΠ1 (I1 ) (b) objΠ1 (I1 , g(f (I1 ), t)) ≤ objΠ2 (I2 , t) ∀t megold´asa az I2 = f (I1 )-nek.
Lemma: Ha Π2 -re ∃ (1 + ε)-approxim´aci´os algoritmus ´es ∃ Π1 < Π2 approxim´aci´ot meg˝orz˝o redukci´o, akkor Π1 -re is ∃ (1 + ε)-approxim´aci´os algoritmus. Bizony´ıt´ as: ∀I1 ∈ Π1 f (I1 ) = I2 ∈ Π2 , I2 -re alkalmazzuk az (1 + ε)-approxim´aci´os algoritmust. Ez ad nek¨ unk egy t megold´ast. objΠ1 (I1 , g(I2 , t)) ≤ objΠ2 (I2 , t) ≤ (1 + ε) · OP TΠ2 (I2 ) ≤ (1 + ε)OP TΠ1 (I1 ) Mindebb˝ol kapjuk, hogy objΠ1 (I1 , s) ≤ (1 + ε) · OP TΠ1 (I1 ). Defin´ıci´ o: Steiner fa probl´ema redukci´oja a metrikus Steiner fa probl´em´ara. Adott I = (G, c, R) a Steiner fa probl´ema egy p´eld´anya, ennek megfeleltetj¨ uk a metrikus Steiner fa I 0 = (G0 , c0 , R0 ) p´eld´any´at, ahol G0 a teljes gr´af V (G) felett, c0 (u, v) = a legr¨ovidebb u ´t hossza u ´es v k¨oz¨ott G-ben, ´es R0 = R. (G0 a c0 -vel teljes´ıti a h´aromsz¨og-egyenl˝otlens´eget). T´ etel: A Steiner-fa probl´ema redukci´oja a metrikus Steiner-fa probl´em´ara meg˝orzi az approxim´aci´os faktort. Bizony´ıt´ as: Legyen I1 a Steiner-fa probl´em´anak egy tetsz˝oleges p´eld´anya. f (I1 ) = I2 a metrikus Steiner-fa probl´ema illeszked˝o p´eld´anya. 2
Kell: OP TΠ2 (I2 ) ≤ OP TΠ1 (I1 ) Ez teljes¨ ul, mert ha F tetsz˝oleges megold´asa I1 -nek, akkor c0 (F ) ≤ c(F ), ´ıgy ha F -et az I1 optim´alis megold´as´anak v´alasztjuk, ad´odik az ´all´ıt´as. Legyen F 0 tetsz˝oleges megold´asa I2 -nek. g(I2 , F 0 ) = F megold´asa I1 -nek, melyet u ´gy kapunk F 0 -b˝ol, hogy minden e ∈ F 0 ´elet kicser´elj¨ uk az ´el hossz´at meghat´aroz´o legr¨ovidebb u ´tra G-ben. Ha a kapott ´elhalmaz nem fa, akkor ´eleket hagyunk el addig, m´ıg f´at nem kapunk. Kell: F megold´asa az I1 -nek, ´es c(F ) ≤ c(F 0 ). Mindk´et k¨ovetelm´eny teljes¨ ul, hiszen ha F 0 lefedi az R cs´ ucsait, akkor F -is, ´es 0 c(F ) ≤ c(F ) k¨ovetkezik a defin´ıci´ob´ol, valamint abb´ol, hogy az ´elek elhagy´as´aval az ´elhalmaz s´ ulya nem n¨ovekedhet, mivel minden ´el s´ ulya nemnegat´ıv. K¨ ovetkezm´ eny: Elegend˝o a metrikus esettel foglalkozni. T´ etel: Adott a metrikus Steiner-fa probl´ema egy tetsz˝oleges p´eld´anya az n pont´ u teljes gr´af f¨ol¨ott. Ekkor az R feletti minim´alis fesz´ıt˝ofa s´ ulya ≤ 2 · OP T . Bizony´ıt´ as: Legyen F optim´alis megold´as.
El˝osz¨or megdupl´azzuk az ´eleket: F 0
3
Mivel minden cs´ ucs foksz´ama p´aros F 0 -ben, ez´ert l´etezik Euler-k¨or F 0 -ben. Az Euler-k¨ort bej´arva, ´es a V \ R cs´ ucsokat ´atugorva kapunk egy C k¨ort az R cs´ ucsai felett.
Tetsz˝oleges ´elet elhagyva C-b˝ol egy FR fesz´ıt˝of´at kapunk R felett. Az R feletti minim´alis s´ uly´ u fesz´ıt˝ofa s´ ulya ≤ c(FR ) ≤ c(C) ≤ c(F 0 ) = 2 · c(F ) = 2 · OP T
TSP - Utaz´ ou ¨ gyn¨ ok probl´ ema Adott egy G = (V, E) gr´af ´es egy c : E → Q + s´ ulyf¨ uggv´eny az ´eleken. Keres¨ unk egy minim´alis s´ uly´ u Hamilton-k¨ort G-ben. T´ etel: A TSP-t nem lehet semmilyen p(n) polinom hib´aval k¨ozel´ıteni, hacsak P = NP. Bizony´ıt´ as: Hamilton-k¨or probl´ema: Van egy G gr´afunk. Ebb˝ol csin´alunk egy TSP probl´em´at teljes n pont´ u gr´af felett. Kn teljes gr´af. (a) Ha e ∈ E(G) ⇒ c(e) = 1 (b) Ha e ∈ / E(G) ⇒ c(e) = n · p(n) Ha G-ben van Hamilton-k¨or, akkor OP TT SP = n. Ha G-ben nincs Hamilton-k¨or, akkor OP TT SP ≥ n · p(n) + 1. Ha a Hamilton probl´em´ara a v´alasz IGEN, akkor az approxim´aci´os algoritmus adna egy megold´ast, aminek a k¨olts´ege ≤ n · p(n). Ha a Hamilton probl´em´ara a v´alasz NEM, akkor az approxim´aci´os algoritmus csak n · p(n) + 1-n´el nagyobb k¨olts´eg˝ u megold´ast adhat, mivel ilyenkor az optimumra als´o korl´at a n · p(n) + 1. Teh´at ha l´etezne egy polinom idej˝ u, ´es p(n) hib´aj´ u approxim´aci´os algoritmus a TSP probl´em´ara, azzal el tudn´ank d¨onteni a Hamilton k¨or probl´em´at polimon id˝oben, ami azt bizony´ıtan´a, hogy P = NP. 4
Metrikus eset Metrikus TSP: c(u, v) + c(v, w) ≤ c(u, w) ∀u, v, w ∈ V ´ enyes a 4-egyenl˝otlens´eg.) (Erv´ Approxim´aci´os algoritmus TSP-re 4-egyenl˝otlens´eggel: I. Keress¨ unk egy minim´alis fesz´ıt˝of´at. (Ennek s´ ulya ≤ OP TT SP ) II. Megdupl´azzuk az ´eleit. III. A kapott Euler-gr´afban keres¨ unk egy Euler-k¨ort, majd az Euler k¨ort bej´arva, a m´ar ´erintett cs´ ucsokat a´tugorva meghat´arozunk egy Hamilton k¨ort. Az ”ugr´as” azt jelenti, hogy ha az Euler k¨or bej´ar´asa sor´an olyan cs´ ucshoz ´er¨ unk, amit m´ar kor´abban megl´atogattunk, akkor azt a´tugorjuk, ´es az Euler k¨or k¨ovetkez˝o ´el´en folytatjuk a bej´ar´ast. Vegy¨ uk ´eszre, hogy a 4-egyenl˝otlens´eg miatt, az ugr´assal a k¨or hossza nem n¨ovekedhet. ´ ıt´ All´ as: A kapott Hamilton-k¨or hossza ≤ 2 · OP T . (Ez 2-approxim´aci´os lenne, de van enn´el jobb is.) Christofides algoritmusa: I. Keress¨ unk egy minim´alis fesz´ıt˝of´at G-ben: F . II. Legyen V 0 az F p´aratlan fok´ u cs´ ucsainak halmaza. III. Mivel |V 0 | = 2k ⇒ ∃ teljes p´aros´ıt´as V 0 felett. Keress¨ unk egy minim´alis s´ uly´ u teljes p´aros´ıt´ast V 0 felett. IV. (V, F ∪ M ) egy Euler-gr´af. Keres¨ unk egy Euler-k¨ort (V, F ∪ M )-ben. V. cs´ ucsok ´atugr´as´aval keres¨ unk egy Hamilton-k¨ort: C. VI. Eredm´eny: C. ´ ıt´ All´ as: c(C) ≤
3 · OP TT SP 2
Bizony´ıt´ as: 1. c(F ) ≤ OP TT SP 2. c(M ) ≤
1 2
· OP TT SP 5
3. c(C) ≤ C(F ∪ M ) Az 1. teljes¨ ul, mivel a minim´alis fesz´ıt˝ofa hossza als´o korl´at az optimum ´ert´ek´ere. A 3. k¨ovetkezik a 4-egyenl˝otlens´egb˝ol. Most bel´atjuk a 2. pontot. Tekints¨ unk egy optim´alis Hamilton k¨ort. Ez ´erinti a V 0 cs´ ucsokat is. Ha a k¨or bej´ar´asa sor´an a´tugorjuk azokat a cs´ ucsokat, melyek V 0 -nek nem elemei, akkor egy olyan CV 0 k¨ort kapunk, melynek hossza nem nagyobb, mint OP TT SP . Tov´abb´a, mivel |V 0 | p´aros elemsz´am´ u, ´ıgy CV 0 k¨or k´et p´aros´ıt´as, M1 ´es M2 , diszjunkt uni´oja.
Teh´at c(CV 0 ) = c(M1 ) + c(M2 ) 1 1 min {c(M1 , c(M2 )} ≤ · c(CV 0 ) ≤ · OP TT SP 2 2 0 Teh´at ha M minim´alis teljes p´aros´ıt´as V felett, akkor c(M ) ≤
1 · OP TT SP 2
P´ elda: n pont´ u gr´af, n p´aratlan
F fesz´ıt˝ofa (s´ ulya n − 1) 6
Mivel k´et p´aratlan fok´ u cs´ ulcsmvan, ezeket o¨sszek¨otj¨ uk a d n2 e s´ uly´ u ´ellel. A kapott n megold´as s´ ulya: (n − 1) + 2
7
Ezzel szemben az optim´alis megold´as egy n hossz´ u k¨or:
Teh´at a Christofides algoritmus olyan megold´ast ad, amely az optimum k¨ozel 32 -szerese: (n − 1) + d n2 e 3 → n 2 Sejt´ es: Metrikus esetre 34 -approxim´aci´o is l´etezik.
8
4. el˝ oad´ as 2012.03.09. Le´ırta: Szajk´ o Anik´ o V´ ag´ asi probl´ em´ ak gr´ afokban Defin´ıci´ o: V´ag´ asi probl´ema: adott G = (V, E) ¨osszef¨ ugg˝o gr´af, c : E → Q+ s´ ulyf¨ uggv´eny ´es S = {s1 , s2 , . . . , sk } ⊆ V. Keres¨ unk C ⊆ E ´elhalmazt u ´gy, hogy C elv´alasztja az s1 , s2 , . . . , sk cs´ ucsokat egym´ast´ol ´es c(C) a lehet˝o legkisebb. Algoritmus: (a) ∀ i-re (i = 1, 2, . . . , k) hat´arozzuk meg azt a minim´alis s´ uly´ u Ci v´ag´ast, ami elv´alasztja si -t a t¨obbi sj (j = 1, 2, . . . , k, j 6= i) cs´ ucst´ol. S S S (b) Legyen c(Ck ) a legnagyobb s´ uly´ u v´ag´as ´es C = C1 C2 . . . Ck−1 . (c) Ekkor az eredm´eny C. Vegy¨ uk ´eszre, hogy C egy megengedett megold´as, hiszen ∀ i-re (i = 1, 2, . . . , k) Ci elv´alasztja si -t a t¨obbi sj -t˝ol (j = 1, 2, . . . , k, j 6= i). Legyen Gi gr´af az a gr´af, amit G-b˝ol az S \ {si } cs´ ucsok ¨osszeh´ uz´as´aval kapunk, ´es jel¨olje si az ¨osszehuz´assal kapott cs´ ucsot. Legyen Ci egy minim´alis s´ uly´ u v´ag´as Gi -ben si ´es si k¨oz¨ott. ´ ıt´ All´ as: Ci minim´alis s´ uly´ u v´ag´as, ami elv´alasztja si -t az S \ {si } cs´ ucsokt´ol G-ben. Bizony´ıt´ as: Indirekt m´odon bizony´ıtunk. Tegy¨ uk fel, hogy ∃Ci′ v´ag´as G-ben, melyre c(Ci′ ) < c(Ci ) ´es Ci′ elv´alasztja si -t az S \ {si } cs´ ucsokt´ol. Ekkor viszont Ci′ Gi -ben is ′ (si , si ) v´ag´as ´ıgy c(Ci ) < c(Ci ), ami ellentmond´as. OP T. T´ etel: Az algoritmus C outputj´ara teljes¨ ul, hogy c(C) ≤ 2 k−1 k A t´etel bizony´ıt´as´ahoz felhaszn´aljuk a k¨ovetkez˝o lemm´at: Lemma: Legyenek a1 , a2 , . . . , ak ∈ R ´es ak = max{a1 , a2 , . . . , ak }. Ekkor a1 + a2 + . . . + ak−1 ≤ k−1 (a1 + a2 + . . . + ak ). k ´ Bizony´ıt´ as: Atrendezve az egyenl˝otlens´eget trivi´alisan ad´odik az eredm´eny. Bizony´ıt´ as: (T´etel) Legyen A egy optim´alis megold´as, azaz az A ´elek elhagy´as´aval a G gr´af k komponensre esik sz´et, G1 , . . . , Gk , ahol si a Gi egy cs´ ucsa. Legyen Ai ⊆ A u ´gy, hogy Ai elv´alasztja si cs´ ucsot a t¨obbi S \ {si } cs´ ucst´ol. Mivel ekkor ∀ ´el Ai -b˝ol pontosan egy m´asik komponensbe megy, ez´ert ∀ e ∈ A ´el pontosan k´et darab Ai , Aj (i 6= j) ´elhalmazba esik. Emiatt k X c(Ai ) = 2c(A) = 2OP T. i=1
Azt is tudjuk, hogy c(Ci ) ≤ c(Ai ) mivel Ci is elv´alasztja si -t az S \ {si } cs´ ucsokt´ol ´es Ci minim´alis s´ uly´ u az ilyen tulajdons´ag´ u v´ag´asok k¨oz¨ ul. c(C) ≤
k−1 X i=1
k−1 k−1 k−1X c(A) = 2 OP T, c(Ai ) = 2 c(Ci ) ≤ k i=1 k k k
1
ahol az els˝o egyenl˝otlens´eg⇐⇒ egyenl˝os´eg, ha a C1 , C2 , . . . , Ck−1 halmazok diszjunktak. A m´asodik egyenl˝otlens´eg a lemm´ab´ol k¨ovetkezik. Megjegyz´ es: Az algoritmus elemz´ese ´eles, erre egy p´eld´at a 1. ´abra mutat. A gr´af tartalmaz egy k hossz´ u k¨ort, melyben minden ´el s´ ulya 1 ´es a k¨or minden cs´ ucs´ab´ol pontosan egy 2 − ε s´ uly´ u ´el indul ki egy egyfok´ u ponthoz. Legyen S a gr´ a fban a k¨ o r¨ on k´ıv¨ uli cs´ ucsok S S S halmaza. Ekkor OP T = k ´es c(Ci ) = 2 − ε, ´ıgy c(C1 C2 . . . Ck−1 ) = (k − 1)(2 − ε).
2-Ɛ
2-Ɛ 1 1
1 2-Ɛ
2-Ɛ
1
1
2-Ɛ
2-Ɛ
´ 1. ´abra. Eles p´elda k-ra. Defin´ıci´ o: k utas v´ag´ as: adott egy G = (V, E) ¨osszef¨ ugg˝o gr´af, c : E → Q+ s´ ulyf¨ uggv´eny ´es egy k ≥ 2 eg´esz sz´am. Keresend˝o C ⊆ E ´elhalmaz, melyre (V, E \ C) k komponens˝ u gr´af ´es c(C) a lehet˝o legkisebb. Defin´ıci´ o: Adott G = (V, E) ¨osszef¨ ugg˝o gr´af ´es c : E → Q+ s´ ulyf¨ uggv´eny. A T = (V, F ) f´at a G gr´af Gomory-Hu f´aj´anak nevezz¨ uk a c s´ ulyf¨ uggv´enyre n´ezve, ha minden e = (u, v) ∈ F ´elre teljes¨ ul, hogy δ(U ) egy minim´alis kapacit´as´ u v´ag´as G-ben, ahol U egyik komponense a T − e k´et ¨osszef¨ ugg˝o komponensb˝ol ´all´o gr´afnak. A T ´elei nem felt´etlen¨ ul G ´elei k¨oz¨ ul ker¨ ulnek ki. Defini´alhatunk egy c′ kapacit´ast a T ´eleire, m´egpedig legyen c′ (e) = c(δ(U )), ahol e ´es U a defin´ıci´o szerinti ´el, ´es v´ag´as. Ekkor tetsz˝oleges u, v ∈ V cs´ ucsokra teljes¨ ul, hogy a minim´alis kapacit´asa az u ´es v cs´ ucsokat elv´alaszt´o v´ag´asnak G-ben, egyenl˝o az u − v cs´ ucsokat ¨osszek¨ot˝o T -beli u ´ton a minim´alis ´elkapacit´assal. Algoritmus: (a) Meghat´arozunk egy (T, c′ ) Gomory-Hu f´at (G, c)-ben. (b) Legyenek C1 , . . . , Ck−1 az els˝o k − 1 legkisebb c′ (e⋆i ) s´ uly´ u ´elhez tartoz´o v´ag´as G-ben. S S (c) C = C1 . . . Ck−1 . (d) Eredm´eny C. 2
A 2. ´abr´an l´athatunk egy p´eld´at k = 4-re. T a G gr´af egy Gomory-Hu f´aja, ekkor az optim´alis megold´as egy 4 ¨osszs´ uly´ u ´elhalmaz, m´egis az algoritmus kimenete egy 3 ∗ (2 − ε) s´ uly´ u ´elhalmaz.
2. a´bra. P´elda k = 4-re. T´ etel: c′ (C) ≤ 2 k−1 OP T k Bizony´ıt´ as: Legyen A optim´alis v´ag´as megold´asa a feladatnak. Ekkor (V, E \ A) kkomponens˝ u gr´af. Legyenek G1 = (V1 , E1 ), . . . , Gk = (Vk , Ek ) a (V, E \ A) komponensei. Tov´abb´a legyen Ai ⊆ A, melyre teljes¨ ul, hogy Ai elv´alasztja Vi cs´ ucshalmazt a t¨obbi Vj (i 6= j) cs´ ucshalmazt´ol. Ekkor nyilv´anval´oan: k X c(Ai ) = 2c(A). i=1
Legyen az ´altal´anoss´ag megszor´ıt´asa n´elk¨ ul c(Ak ) ≥ c(Ai ), i = 1, . . . , k − 1. Vegy¨ uk egy T Gomory-Hu f´aj´at a G gr´afnak, majd h´ uzzuk ¨ossze minden Vi cs´ ucshalmazt egyetlen pontt´a. Ekkor a Gomory-Hu fa ´elei az ¨osszeh´ uzott Vi cs´ ucsokat k¨otik ¨ossze, illetve hurok´elekk´e is v´alhatnak az ¨osszeh´ uz´as sor´an. Mindenesetre ´elek elhagy´as´aval T -b˝ol egy fesz´ıt˝of´at kapunk az ¨osszeh´ uzott gr´afban, legyen ez B. Mivel B fa, az ´eleit ir´any´ıthatjuk Vk⋆ fel´e. Jel¨olje ei ∈ B a Vi -b˝ol a Vj -be mutat´o ´elet. Tegy¨ uk fel, hogy ei ´el a vi ∈ Vi ´es vj ∈ Vj cs´ ucsokat k¨oti ¨ossze G-ben (ilyen cs´ ucsok l´eteznek, hiszen ei a T egy ´el´eb˝ol ′ keletkezett). Mivel c (ei ) az eiP´el s´ ulya a T Gomory-Hu f´aban, ´es Ai ´elhalmaz egy ui − vi k−1 ′ ⋆ v´ag´as, c′ (ei ) ≤ c(Ai ). Legyen i=1 c (ei ) a Gomory-Hu f´aban a k − 1 legkisebb s´ uly´ u ´elek ´ s´ uly´anak ¨osszege. Igy c(C) ≤
k−1 X i=1
c
′
(e⋆i )
≤
k−1 X i=1
′
c (ei ) ≤
k−1 X i=1
k−1X k−1 k−1 c(Ai ) ≤ c(Ai ) = 2c(A) = 2 OP T. k i=1 k k k
3
3. ´abra. Az A v´ag´as ´altal sz´etv´alasztott komponensek a gr´afban ´es az ´ıgy kapott gr´af egy Gomory-Hu f´aja.
A 2. ´abra olyan p´eld´at mutat, ahol OP T = k, de az algoritmus eredm´enye (2−ε)(k −1), teh´at az algoritmus elemz´ese pontos.
4
´ 5. El˝ oad´ as, 2012.04.06. Le´ırta: Csaba Akos Motiv´ aci´ o Tegy¨ uk fel, hogy egy v´arosban K db t˝ uzolt´o´allom´ast szeretn´enk l´etes´ıteni u ´gy, hogy a t˝ uzolt´ok a saj´at k¨orzet¨ ukben minden h´azhoz oda´erjenek legfeljebb 5 perc alatt. Metrikus K-k¨ ozpont probl´ ema G = (V, E) legyen egy teljes gr´af, c : E → R+ , olyan s´ ulyf¨ uggv´eny az ´eleken, ami teljes´ıti a h´aromsz¨og egyenl˝otlens´eget, K ∈ N k¨ozpontok sz´ama (fix). Legyen d(u, S) = minv∈S {c(u, v)}. Keress¨ uk S ⊆ V cs´ ucshalmazt, amire: • |S| ≤ K • maxu∈V {d(u, S)} minim´alis Defin´ıci´ o: Domin´ans halmaz: G-ben D ⊆ V (G) domin´ans halmaz, ha ∀v ∈ V \ D pontnak ∃u ∈ D szomsz´edja. (∃(u, v) ∈ E) P´ elda: 1 elem˝ u domin´ans halmaz
P´ elda: Domin´ans halmaz u ´t eset´en
1
Defin´ıci´ o: dom(G) = min{|D| : D domin´ans halmaz G-ben }. Defin´ıci´ o: G2 : Legyen G gr´af, G2 = G ∪ {(u, v) : ∃u → w → v 2 hossz´ uu ´t G-ben} P´ elda: egy G2 gr´af egy u ´t eset´en
Rendezz¨ uk az ´elindexeket a c szerint: c(e1 ) ≤ c(e2 ) ≤ · · · ≤ c(em ) Legyen Ei = {e1 , . . . ei } az els˝o i db legkisebb s´ uly´ u ´el halmaza, tov´abb´a Gi = (V, Ei ), ´ıgy Gm = G. Megjegyz´ es: min {i ∈ {1, . . . , m} : dom(Gi ) ≤ K} kisz´am´ıt´asa ekvivalens a metrikus K-k¨ozpont probl´em´aval Lemma: Ha I f¨ uggetlen ponthalmaz H 2 -ben, akkor dom(H) ≥ |I|. Biz D legyen optim´alis domin´ans halmaz H-ban.
Ekkor H 2 -ben van |D| db klikk:
2
Ha I f¨ uggetlen H 2 -ben (antiklikk) , akkor mind a |D| db klikkb˝ol I legfeljebb 1 pontot tartalmaz. Azaz |I| ≤ |D|.
Algoritmus 1. Hat´arozzuk meg a G21 , . . . , G2m gr´afokat 2. Minden G2i -ben hat´arozzunk meg egy maxim´alis Mi f¨ uggetlen ponthalmazt (nem b˝ov´ıthet˝o tov´abb) 3. Legyen 1 ≤ j ≤ m a legkisebb index , hogy |Mj | ≤ K 4. Eredm´eny: Mj Lemma: Ha j a v´alasztott index a 3. l´ep´esben, akkor c(ej ) ≤ OPT Biz ∀i < j-re |Mi | > K a j v´alaszt´asa miatt. Az el˝oz˝o lemma miatt: dom(Gi ) ≥ |Mi | > K Ez´ert ha i∗ optim´alis megold´asa az ´atfogalmazott metrikus K-k¨ozpont probl´em´anak, akkor i∗ ≥ j. Teh´at OPT = cei∗ ≥ c(ej ). T´ etel: Az algoritmus 2-approxim´aci´o a metrikus K-k¨ozpont probl´em´ara. Biz Mj domin´ans G2j -ben: Indirekt, ha ∃v ∈ V (G2j ) \ Mj , ami nem szomsz´edos egyik Mj -beli ponttal sem G2j -ben, akkor Mj nem maxim´alis.
3
Legyen v ∈ / Mj . Ekkor ∃u ∈ Mj , melyre (u, v) ∈ E(G2j ). Megmutatjuk, hogy c(u, v) ≤ 2c(ej ). Ha (u, v) ∈ Gj , akkor c(u, v) ≤ c(ej ) a Gj defin´ıci´oja miatt. Ha (u, v) ∈ / Gj , akkor ∃w ∈ V (G), melyre (v, w), (w, v) ∈ Gj (azaz l´etezik 2 hossz´ uu ´t Gj -ben, amelynek v´egpontjai u ´es v). Ekkor c(u, w), c(w, v) ≤ c(ej ) miatt, a h´aromsz¨og-egyenl˝otlens´eget haszn´alva kapjuk, hogy c(u, v) ≤ c(u, w) + c(w, v) ≤ 2c(ej ). V´eg¨ ul, mivel Mj domin´ans G2j gr´afban, ´es V (G) = V (G2j ), k¨ovetkezik, hogy G gr´afban minden Mj -n k´ıv¨ uli cs´ ucs Mj -t˝ol legfeljebb 2c(ej ) t´avols´agra van. P´ elda: Az algoritmus nem jobb, mint 2-approxim´aci´o
Adott egy Ker´ek-gr´af, amiben minden t´avols´ag 2, kiv´eve a k¨oz´eps˝o cs´ ucs t´avols´aga a t¨obbi cs´ ucshoz, ami 1. Ekkor c metrikus s´ ulyf¨ uggv´eny. Legyen. K := 1. Ekkor az OPT = 1 (a k¨oz´eps˝o cs´ ucs). Az algoritmus fut´asa:
Ha a bekarik´azott cs´ ucsot v´alasztjuk maxim´alis f¨ uggetlen ponthalmaznak, akkor az algoritmus 2-¨ot ad, teh´at az optimum k´etszeres´et. 4
Lemma: Ha P 6= NP , akkor nincs 2 − approxim´aci´os algoritmus a K-k¨ozpont probl´em´ara. Biz Domin´ans halmaz probl´ema: Adott G gr´af, K eg´esz sz´am. Van-e legfeljebb K m´eret˝ u domin´ans halmaz G-ben ? (NP teljes) H legyen teljes gr´af G pontjai felett 1 ha e ∈ E(G) c(e) = 2 ha e ∈ / E(G) H, c, K legyenek a metrikus K-k¨ozpont probl´ema param´eterei (c teljes´ıti a h´aromsz¨og egyenl˝otlens´eget) Tegy¨ uk fel l´etezik 2 − approxim´aci´os algoritmus a metrikus K-k¨ozpont probl´em´ara, ami polinomi´alis idej˝ u. a´ll´ıt´as: A 2 − approx. algoritmussal el lehet d¨onteni a domin´ans halmaz probl´em´at • Ha dom(G) ≤ K, azaz ∃D ⊆ V (G) domin´ans, amire |D| ≤ K, akkor a metrikus K-k¨ozpont optimum ´ert´eke H-ban 1. • Ha dom(G) > K , akkor az optimum ´ert´eke a metrikus K-k¨ozpont probl´em´anak 2. Azaz a 2 − approxim´aci´os algoritmus eld¨onti a domin´ans halmaz probl´em´at G-ben polinom id˝oben, ´ıgy P = NP, ellentmond´as.
A probl´ ema ´ altal´ anos´ıt´ asa Legyen G teljes gr´af, c egy h´aromsz¨og egyenl˝otlens´eget teljes´ıt˝o s´ ulyf¨ uggv´eny, W konstans, + w : V (G) → R cs´ ucsf¨ uggv´eny (t˝ uzolt´o´allom´as l´etes´ıt´es´enek k¨olts´ege egy cs´ ucsban) adottak. Olyan D ⊆ V (G)-t keres¨ unk, amire: • w(D) ≤ W (t˝ uzolt´oa´llom´asok l´etes´ıt´es´enek ¨osszk¨olts´ege ≤ W ) • maxv∈V d(v, D)
minim´alis
Az el˝oz˝oekhez hasonl´oan hossz szerint nem-cs¨okken˝o sorrendbe rendezz¨ uk az ´eleket: c(e1 ) ≤ · · · ≤ c(em ) Ei = {e1 , . . . , ei }
Gi = (V, Ei )
Legyen Ni (v) = {u ∈ V : ∃(u, v) ∈ Ei }. Defin´ıci´ o: Gi gr´afban a legkisebb s´ uly´ u cs´ ucs v szomsz´eds´ag´aban si (v) = argmin{w(u) : u ∈ Ni (v) ∪ {v}}.
5
Megjegyz´ es: ucsainak a legkisebb Ha I f¨ uggetlen halmaz G2i -ben, akkor S(I) = {si (u) : u ∈ I} az I cs´ s´ uly´ u szomsz´edai Gi -ben. Defin´ıci´ o: wdom(Gi ) wdom(Gi ) = min{w(D) : D
domin´ans halmaz Gi -ben }
´ ıt´ All´ as: wdom(Gi ) ≥ w(S(I)), ahol I f¨ uggetlen ponthalmaz G2i -ben. Biz Ha D optim´alis domin´ans halmaz Gi -ben, akkor G2i az ´abra szerinti lesz:
Mivel I f¨ uggetlen cs´ ucshalmaz G2 gr´afban, minden klikkb˝ol maximum egy cs´ ucsot tartalmaz. Teh´at w(S(I)) ≤ w(D), mivel az I cs´ ucsainak szomsz´edai k¨oz¨ott szerepelnek a D cs´ ucsai.
Algoritmus az ´ altal´ anos´ıtott probl´ em´ ara: 1. Hat´arozzuk meg a G21 , . . . , G2m gr´afokat 2. Minden G2j -ben keress¨ unk Mj maxim´alis f¨ uggetlen ponthalmazt 3. Legyen j a minim´alis index, amire w(S(Mj )) ≤ W 4. Eredm´eny: S(Mj ) ´ ıt´ All´ as: Az algoritmus 3-approxim´aci´o. Biz Hasonl´oan a w ≡ 1 esethez (el˝oz˝o probl´ema), c(ej ) ≤ OPT. Tudjuk, hogy Mj domin´ans G2j -ben. 6
Megmutatjuk, hogy G-ben minden cs´ ucs S(Mj )-t˝ol ≤ 3c(ej ) t´avols´agra van. Legyen v ∈ / Mj . Mivel Mj domin´ans G2j gr´afban, ∃u ∈ Mj , melyre (u, v) ∈ E(G2j ). Megmutatjuk, hogy c(s(u), v) ≤ 3c(ej ). Egyr´eszt tudjuk, hogy c(u, v) ≤ 2c(ej ) (l´asd a w ≡ 1 esetet). M´asr´eszt (s(u), u) ∈ E(Gj ) defin´ıci´o szerint. Teh´at c(s(u), u) ≤ c(ej ). A h´aromsz¨og egyenl˝otlens´eg miatt c(s(u), v) ≤ c(s(u), u) + c(u, v) ≤ 3c(ej ). P´ elda: Az algoritmus nem jobb, mint 3-approxim´aci´o
A be nem rajzolt ´elek hosszai a v´egpontjaik k¨oz¨ott vezet˝o legr¨ovidebb utak hossza. Az algoritmus sor´an Gn+3 -ig kell elmenni, erre teljes¨ ul el˝osz¨or, hogy w(S(Mn+3 )) ≤ W .
7
Ha B-t v´alasztjuk maxim´alis f¨ uggetlen ponthalmaznak G2n+3 -ban: Mn+3 = {B}, ´es S(Mn+3 ) = {A}. Mivel A maxim´alis t´avols´aga a t¨obbi pontt´ol 3, ez´ert az algoritmus eredm´enye 3 lesz. Az optim´alis megold´as: {A, B} ´es OPT = 1 + . Teh´at, az algoritmus eredm´enye
3 1+
× OPT .
8
6. El˝ oad´ as, 2012. 03. 31. Le´ırta: Hetei Bal´ azs Prim´ al-Du´ al s´ ema IP probl´ ema: min cx Ax ≥ b x≥0 x ∈ {0, 1}n LP relax´ aci´ o
Du´ al LP
min cx
max by
Ax ≥ 0
yA ≤ c
x≥0
y≥0
Komplementarit´ asi felt´ etelek: Prim´al: xj > 0 =⇒
X
aij yi = cj
i
Du´al: yi > 0 =⇒
X
aij xj = bi
j
Relax´ alt komplementarit´ asi felt´ etelek: α-relax´alt prim´al felt´etel: xj > 0 =⇒ cj /α ≤
X
aij yi ≤ cj
i
β-relax´alt du´al felt´etel: yi > 0 =⇒ bi ≤
X
aij xj ≤ βbi
j
a speci´alis α = 1, β = 1 esetben az eredeti komplementarit´asi felt´eteleket kapjuk vissza
1
´ ıt´ All´ as: Tegy¨ uk fel, hogy x¯ ´es y¯ prim´al, illetve du´al megengedett megold´asok, amelyek teljes´ıtik az α-relax´alt prim´al ´es a β-relax´alt du´al komplementarit´asi felt´eteleket. Ekkor: c¯ x ≤ αβb¯ y Bizony´ıt´ as: c¯ x=
n X
cj x¯j ≤
j=1
n X
(α
j=1
X
aij y¯i )¯ xj = α
i
XX X ( aij x¯j )¯ yi ≤ αβ bi y¯i = αβb¯ y i
j
i
P´ elda (Halmazfed´ es): E alaphalmaz S = {S1 , ..., Sk } (Si ⊆ E) c : S → R+ Eg´esz´ert´ek˝ u program: min cS xS S
P
xS ≥ 1 (∀e ∈ E)
S:e∈S
xS ∈ {0, 1} (∀S ∈ S) LP relax´aci´o: P min cS xS
Du´al LP: P max ye e
S
P
P
xS ≥ 1 (∀e ∈ E)
ye ≤ ce (∀S ∈ S)
S:e∈S
e:e∈S
xS ≥ 0
y≥0
Legyen a maxim´alis elem gyakoris´ag f max |{S : e ∈ S}| = f e
Algoritmus (Prim´ al-Du´ al s´ ema a halmazfed´ esre): (a) x¯ = 0, y¯ = 0, minden e ∈ E fedetlen (b) am´ıg van E-ben fedetlen elem 2
(c) Legyen e ∈ E fedetlen n¨ovelj¨ uk y¯e ´ert´ek´et, am´ıg nem s´ert¨ unk egyetlen du´al felt´etelt sem (d) minden olyan du´al felt´etel, amely egyenl˝os´eggel teljes¨ ul y megold´asban (S halmazok) =⇒ x¯S = 1 (e) ∀e : ha van olyan S ∈ S, hogy e ∈ S, ´es x¯S = 1, akkor legyen e fedett (f) ciklus v´ege (g) eredm´eny: {S : x¯S = 1} ´ ıt´ All´ as: x¯ prim´al megengedett, y¯ du´al megengedett megold´as az algoritmus v´eg´en, ´es α = 1, β = f -re teljes´ıti a relax´alt prim´al ´es du´al kompementarit´asi felt´eteleket Bizony´ıt´ as: Mivel az algoritmus akkor ´all meg, ha minden elem fedett, azaz ∀e ∈ E-hez van olyan S ∈ S, hogy x¯S = 1 ´es e ∈ S =⇒ x¯ prim´al megengedett y¯ a v´alaszt´asa miatt du´al megengedett prim´al rendben van P du´alhoz kell m´eg: y¯e > 0 =⇒ 1 ≤ x¯S ≤ f S:e∈S
minden ¨osszeg maximum f tag´ u, mivel a max. elem gyakoris´ag f T´ etel: A Prim´al-Du´al s´ema f -approxim´aci´o Bizony´ıt´ as: x¯ prim´al megengedett ´es eg´esz (¯ x ∈ {0, 1}n ) Az el˝oz˝o a´ll´ıt´as miatt teljes´ ıti a relax´alt komplementarit´asi felt´eteleket α = 1, β = f melP lett =⇒ c¯ x≤f y¯e ≤ f · OP T e P y¯e ≤ Du´al OP T = Prim´al LP relax´alt OP T ≤ OP T (eg´esz) e
T¨ obbsz¨ or¨ os v´ ag´ asok ´ es t¨ obbterm´ ekes folyamok f´ akon G = (V, E) fa (egyszer˝ u, ¨osszef¨ ugg˝o, k¨ormentes gr´af) + c:E→Z (s1 , t1 )...(sk , tk ) forr´as-nyel˝o p´arok si , ti ∈ V (∀i = 1...k) T¨obbsz¨or¨os v´ag´as: D ⊆ E, ami ∀si , ti p´art elv´alaszt (azaz (V, E − D) gr´afban az si ´es ti cs´ ucsok k¨ ul¨on o¨sszef¨ ugg˝o komponensbe esnek ∀i = 1...k) Mivel G fa: ∀si , ti p´arra ∃! Pi u ´t, ami o¨sszek¨oti o˝ket G-ben C´el: t¨obbsz¨or¨os v´ag´as min
P
ce d e
e∈E
P
de ≥ 1 (∀i = 1...k)
e∈Pi
3
de ∈ {0, 1} ∀e LP relax´ alt: P min ce d e e∈E
P
de ≥ 1 (∀i = 1...k)
e∈Pi
de ≥ 0 Du´al: max
k P
fi
i=1
P
fi ≤ ce (∀e ∈ E)
i:e∈Pi
fi ≥ 0 (folyam az si , ti p´arok k¨oz¨ott) P´ elda: s1 , t3
u K A A A A 1 1 1 A2 2 A u "b 1 A " b " b A 1 b " u -b Au "
s2 , t1
1 2
s3 , t2 ce ≡ 1, |D| = 2, k´ekek: optim´alis (t¨ort) folyamok =⇒
(Ford-Fulkerson nem teljes¨ ul) s1 , t3
u K A A A A 1 1 A0 A u "b 1 A b "" b A 1 b " u -b Au "
s2 , t1
0
s3 , t2 Eg´esz folyam: OP T (fint ) = 1
4
3 2
G-nek kiv´alasztunk egy r gy¨ok´erelemet. v cs´ ucs m´elys´ege a v-r u ´t hossza. Az si , ti cs´ ucsok legkisebb k¨oz¨os o˝se a Pi u ´ton a legkisebb m´elys´eg˝ u elem. Vezess¨ uk be az lk¨o(i) ∈ V jel¨ol´est a legkisebb k¨oz¨os o˝sre. Egy e ´el m´elys´eg´et a cs´ ucsokkal anal´og m´odon defini´aljuk. Algoritmus: (a) d¯ = 0, f¯ = 0, D = ∅ (b) J´arjuk be a gy¨okeres fa cs´ ucsait m´elys´eg szerint nem n¨ovekv˝o sorrendben (legm´elyebbel kezdj¨ uk). Legyen v a k¨ovetkez˝o cs´ ucs a bej´ar´asban ∀i = (1...k) : lk¨o(i) = v N¨ovelj¨ uk f¯i -t, am´ıg lehet (nem s´ert du´al felt´etelt). Legyenek ei,1 ...ei,k olyan ´elek, amelyek szoross´a v´altak (a du´al felt´etel egyenl˝os´eggel teljes¨ ul) f¯i n¨ovel´ese sor´an D = D ∪ {ei,1 ...ei,k } (c) ciklus v´ege (d) D = {e1 ...et }, az ´eleket a hozz´aad´as szerint kronologikus sorrendben indexelj¨ uk (e) T¨or¨olj¨ unk ´eleket ford´ıtott kronologikus sorrendben D-b˝ol: j = t...1, ha D \ {ej } t¨obbsz¨or¨os v´ag´as =⇒ D = D \ {ej }, k¨ ul¨onben a megel˝oz˝o ´ellel folytatjuk (f) eredm´eny: D, f¯, d¯e =
1 0
e∈D e∈ /D
´ ıt´ All´ as: Ha f¯i > 0 =⇒ !v = lk¨o(i), legfeljebb egy e ∈ D van az si egy e ∈ D van az v ti u ´ton. u @
v u e1 u
@ @
vu ´ton, ´es legfeljebb
e1 ∈ D e2 ∈ D @ @u
@ e @ @2 @ @ @u
si ti Bizony´ıt´ as: Csak az a´ll´ıt´as els˝o fel´et bizony´ıtjuk, a m´asosik r´esz anal´og. Indirekt tegy¨ uk fel, hogy ∃ e, e0 ´el az si vu ´ton, hogy e, e0 ∈ D
5
v
u @
0
e uu
@ e00 e @ u @ @ @u @u u @
u =lk¨o(j) @ @
@ @u
ti
si sj tj Tegy¨ uk fel, hogy e m´elyebben van, mint e0 . Mivel e ´elt nem t¨or¨olt¨ uk D-b˝ol =⇒ ∃ sj − tj 0 p´ar, amit csak e v´alaszt el. lk¨o(j) az e ´es az e k¨oz¨ott van, k¨ ul¨onben e0 elv´alasztja o˝ket. 00 Legyen e az az ´el, ami szoros a Pj u ´ton az sj tj feldolgoz´asa ut´an. Tudjuk, hogy u cs´ ucsot kor´abban dolgoztuk fel, mint v cs´ ucsot, mivel m´elyebben van. ¯ fi > 0 =⇒ az e ´el az si ti p´ar feldolgoz´asa ut´an ker¨ ult D-be. Azonban ekkor e k´es˝obb ker¨ ult D-be, mint e00 . Teh´at e t¨or¨olhet˝o lenne, mert e00 ∈ D elv´alasztja az sj − tj p´art, ami ellentmond az indirekt feltev´esnek. ´ ıt´ All´ as: f¯, d¯ prim´al, du´al megold´asok, amik teljes´ıtik az α = 1, β = 2 mellett a relax´alt prim´al ´es du´al komplementarit´asi felt´eteleket Bizony´ıt´ as: f¯ ´es d¯ megengedetts´eg´et az algoritmus garant´alja (a ciklus magban f¯ sosem s´erti a du´al felt´eteleket). D a ciklus v´eg´enPt¨obbsz¨or¨os v´ag´as =⇒ d¯ megengedett megold´as. d¯e ≤ 2 β = 2. Az el˝oz˝o ´all´ıt´as miatt f¯i > 0 =⇒ e∈Pi
lk¨o(i) = v
u @ d¯ 0 = 1 e @ @ @ @ 1−1 @u ´el lehet @
d¯e = 1 u
si ti T´ etel: Az algoritmus 2-approxim´aci´o a t¨obbsz¨or¨os v´ag´as probl´em´ara, ´es 21 -approxim´aci´o ´ az eg´esz t¨obbterm´ekes folyam probl´em´ara FAKON Bizony´ıt´ as: P P ¯ ¯ ¯ f ´es d eg´esz megold´asok, megengedettek, ´es ce de ≤ 2 f¯i (az el˝oz˝o ´all´ıt´as miatt) e i P P¯ P ¯ fi ≤ Du´al LP OP T = Prim´al LP OP T ≤ Prim´al eg´esz OP T ≤ c¯e de ≤ 2 f¯i e
i
Erre ´eles p´elda a m´ar kor´abban l´atott a´bra.
6
i
7. Előadás, 2012.04.13. Leírta: Horváth Vanda Metrikus telephely elhelyezési probléma Feladat: Adott telephelyek F halmaza, és városok C halmaza. Az alapfeladat az, hogy néhány telephely megnyitásával szeretnénk ellátni a városokat a lehető legkisebb költséggel. A költség a következőkből adódik: fi : az i telephely megnyitási költsége cij : annak a költsége, ha a j várost az i telephelyhez kötjük Feltesszük, hogy c teljesíti a háromszög-egyenlőtlenséget. (Vegyük észre, hogy c nincsen konkrétan megadva például két város között, de a háromszög-egyenlőtlenséget csak olyan esetben fogjuk használni, hogy ez ne legyen zavaró.) IP feladat: min(
XX
cij xij +
fi y i )
i∈F
i∈F j∈C
X
X
xij ≥ 1 ∀j ∈ C
i∈F
yi − xij ≥ 0 ∀i ∈ F ∀j ∈ C yi ∈ {0, 1} ∀i ∈ F xij ∈ {0, 1} ∀i ∈ F ∀j ∈ C Duál LP:
LP relaxált: X XX fi yi ) cij xij + min( i∈F j∈C
X
max
i∈F
X
αj
j∈C
xij ≥ 1 ∀j ∈ C
αj − βij ≤ cij
i∈F
X
yi − xij ≥ 0 ∀i ∈ F ∀j ∈ C yi ≥ 0 ∀i ∈ F xij ≥ 0 ∀i ∈ F ∀j ∈ C
βij ≤ fi
j∈C
Primál komplementaritási feltételek: xij > 0 ⇒ αj − βij = cij yi > 0 ⇒
X
βij = fi
j∈C
Relaxáljuk 1/3-as szorzóval: xij > 0 ⇒
1 cij ≤ αj − βij ≤ cij 3 1
∀i ∈ F ∀i ∈ F
∀j ∈ C
yi > 0 ⇒
X 1 fi ≤ βij ≤ fi 3 j∈C
Ez a múlt óra alapján egy 3-approximáció lenne. Mi most ennél kicsit többet is fölteszünk: βij = fi mindig teljesülni fog az algoritmusban, és sokszor az αj − βij = cij is. Ennek ellenére az algoritmus 3-approximáció lesz, nem jobb.
P
Algoritmus: I. Fázis Kezdetben α ≡ 0, β ≡ 0. Definiáljuk a t időt, amivel az algoritmus eseményeinek időpontját követjük. Egy időegység alatt, ha α vagy β változik, akkor 1-et változik. Kezdetben legyen t = 0, és ez növekszik folyamatosan. A t növekedésével egyszerre kezdjen el az összes α változó is növekedni. Ez addig tart, amíg valamelyik él szoros nem lesz, ahol a szoros definíciója a következő: ha αj = cij valamely j ∈ F -re, akkor az (i, j) él szoros. Ha (i, j) él szorossá vált, onnantól kezdve βij is növekszik az αj növekedésével azonos mértékben. Ha újabb élek válnak szorossá, akkor a hozzájuk tartozó βi0 j is elkezd növekedni. P
Ha valamely i-re j∈C βij = fi teljesül, akkor az i telephely ideiglenesen nyitottá válik, ami a következőt jelenti: az összes i-hez kapcsolódó szoros él végén a j városra αj növelése megáll, és βij növelése is megáll. Az összes ilyen városra i a kapcsolódási tanu. Ha később egy él szorossá válik, és az egyik végén egy ideiglenesen nyitott telephely van, akkor az ilyen város kapcsolódási tanuja is az a telephely. (És ekkor persze a hozzá tartozó α növelése megáll.) II. Fázis Legyen Ft az ideiglenesen nyitott telephelyek halmaza. T = {(i, j) : βij > 0} Ezek a speciális élek. T 2 = {az 1 vagy 2 él hosszú utak T -ben} Definiáljuk a H gráfot a következőképpen: H = (Ft , T 2 |Ft ), vagyis az élei az Ft által feszített élek T 2 -ben. Legyen I egy max független ponthalmaz H-ban. Legyen yi = 1 akkor és csak akkor, ha i ∈ I. I ⊆ Ft és mivel független, ezért domináns is H-ban. Fj := {i ∈ F : (i, j) él speciális (azaz βij > 0)} Állítás: |Fj ∩ I| ≤ 1 2
Bizonyítás: Ha i, i0 ∈ Fj ∩I ⇒ (i, j), (i0 , j) ∈ T ⇒ (i, i0 ) ∈ T 2 ⇒ i, i0 nem függetlenek H-ban, ami ellentmondás. Definiáljuk a φ függvényt a városokon a következőképpen: 1 Ha ∃i ∈ Fj ∩ I, akkor φ(j) := i és xij = 1 2 Legyen a j város kapcsolódási tanuja i telephely és legyen i ∈ I. Ekkor φ(j) := i és xij = 1 3 Legyen a j város kapcsolódási tanuja i telephely és legyen i ∈ / I. Mivel I domi0 0 2 0 náns H-ban, ezért ∃i ∈ I : (i, i ) ∈ T . Ekkor φ(j) := i és xi0 j = 1. Az első két esetben azt mondjuk, hogy a j város direkt kapcsolódik az i telephelyhez, a harmadik esetben pedig azt, hogy a j város indirekt kapcsolódik az i0 telephelyhez. Példa varosok 1 1 1.telephely
2
3 3
f1 = ε
3
3
1 1 1 1
3 n
2.telephely
f2 = (n + 1)ε
1
Legyen n darab város és 2 telephely. Legyen f1 = ε és f2 = (n + 1)ε. Az élek: az i telephelyhez és j városhoz tartozik az (i, j) rendezett pár. c11 = 1, c1j = 3 ∀j ≥ 2 városra, és c2j = 1 ∀j városra. Kezdetben α = 0, β = 0, t = 0, és az α-k elkezdenek növekedni az idővel párhuzamosan. Vizsgáljuk azokat az időpillanatokat, amikor történik valami új. • t = 1: α ≡ 1, β ≡ 0. Szorossá váltak az (1, 1) él, illetve a (2, j) élek ∀j városra • t = 1 + ε: α1 = α2 = . . . αn = 1 + ε, β11 = ε, β2j = ε ∀j ∈ C, az 1-es telephely ideiglenesen nyitottá válik: α1 növelése megáll, az 1-es város kapcsolódási tanuja az 1-es telephely 3
• t=1+ε+
ε : n−1
α1 = 1 + ε, αj = 1 + ε + (Ell: (n − 1)(ε +
ε ) n−1
ε n−1
∀j ≥ 2, β21 = ε, β2j = ε +
ε n−1
∀j ≥ 2
+ ε = (n + 1)ε, vagyis tényleg ekkor érjük el f2 értékét)
Ekkor a 2-es telephely is ideiglenesen nyitottá válik, és a 2, 3, . . . , n városok kapcsolódási tanuja a 2-es telephely lesz. Ekkor a T élek, illetve T 2 élek: varosok 1 2
1.telephely
2.telephely
3
n varosok 1 2
1.telephely
2.telephely
3
n
Ft = {1, 2} H = {az 1 és 2 telephely közötti él} Ekkor I-nek válaszható az 1-es telephely. Ekkor a költség: f1 + c1 1 + Az optimum pedig a 2-es telephely megnyitása: OPT = f2 +
P
P
c1j = ε + 1 + 3(n − 1)
c2j = (n + 1)ε + n.
Ebből a példából látszik, hogy az algoritmus nem is lehet jobb, mint 3-approximáció. (Vagyis ez éles példa.) Az algoritmus elemzése: αj = αjf + αje ahol ezek a következőt jelentik: αjf : a j város ennyit fizet a hozzá kötött telephely megnyitásáért 4
αje : a j város ennyit fizet az (i, j) él használatáért Így αje αjf
(
cij αj
(
βij ha φ(j) = i, és j direkt kapcsolódik i-hez 0 ha φ(j) = i, és j indirekt kapcsolódik i-hez
=
=
ha φ(j) = i, és j direkt kapcsolódik i-hez ha φ(j) = i, és j indirekt kapcsolódik i-hez
Állítás: αjf = fi
X
∀i ∈ I
j∈C,φ(j)=i
Bizonyítás: Tudjuk, hogy X
βij = fi
∀i ∈ I
j∈C,(i,j)∈T
Mivel αjf > 0 ⇔ βij > 0 ezért X
X
βij =
j∈C,(i,j)∈T
αjf
j∈C,φ(j)=i
Állítás: Ha φ(j) = i és j indirekt kapcsolódik i-hez, akkor cij ≤ 3αje Bizonyítás: i0
i ∈T j
0
∈T j
Legyen a j város kapcsolódási tanuja i0 . Ekkor létezik j 0 hogy (i, j 0 ) és (i0 , j 0 ) élek benne vannak T -ben, hiszen (i, i0 ) ∈ T 2 , mivel (i, i0 ) ∈ H gráf. αje = ci0 j , ezért azt szeretnénk belátni, hogy cij ≤ 3ci0 j . Legyenek t1 és t2 azok az időpillanatok, amikor i és i0 telephelyek ideiglenesen nyitottá váltak. Ekkor αj 0 ≤ min{t1 , t2 }, hiszen αj 0 növelése megállt, amikor i, i0 bármelyike nyitottá vált. Másrészről αj 0 > max{cij 0 , ci0 j 0 } mert (i, j 0 ) és (i0 , j 0 ) speciális élek, vagyis βi,j 0 > 0, βi0 j 0 > 0. Továbbá αj ≥ t2 , mert i0 a j város kapcsolódási tanúja. Így αj ≥ t2 > αj 0 > max{cij 0 , ci0 j 0 }. Valamint αj ≥ ci0 j triviálisan igaz. Még azt is vegyük észre, hogy az indirekt kapcsolódás miatt αj = αje . Ezek alapján a háromszög-egyenlőtlenséget alkalmazva kapjuk: cij ≤ cij 0 + ci0 j 0 + ci0 j ≤ 3αj = 3αje 5
Tétel: XX
X
cij xij +
i∈F j∈C
fi y i ≤ 3
i∈F
X
αj
j∈C
Bizonyítás: XX
cij xij ≤ 3
i∈F j∈C
X
αje
j∈C
mert φ(j) = i esetén ha direkt kapcsolódik, akkor cij = αje , ha pedig indirekt kapcsolódik, akkor cij ≤ 3αje , és xij kódolja a φ(j)-t. Másrészt megmutattuk, hogy X
αjf =
3
X j∈C
αj = 3
P
X j∈C
j∈C
αj =
αje + 3
X j∈C
P
αje +
αjf ≥
XX
j∈C
fi
i∈I
j∈C
Felhasználva, hogy
X
P
j∈C
αjf kapjuk
cij xij + 3
X i∈F
i∈F j∈C
6
fi y i ≥
XX i∈F j∈C
cij xij +
X i∈F
fi y i
8. el˝ oad´ as, 2012. 04. 21. Le´ırta: Retek D´ avid Max-SAT probl´ ema Adottak a x1 . . . xn logikai v´altoz´ok, az ezeken ´ertelmezett l1 . . . l2n liter´alok (l2i = xi , l2i+1 = x¯i ), ´es a f¨ol¨ott¨ uk defini´alt K = {c1 . . . cm } kl´ozok egy halmaza. Tov´abb´a adott + a h : K → R0 s´ ulyf¨ uggv´eny, ami minden kl´ozhoz egy nemnegat´ıv sz´amot rendel. Ezen felt´etelek mellett keress¨ uk a v´altoz´oknak egy olyan y1 . . . yn igazs´ag´ert´ekel´es´et, amelyb az IGAZ ´ert´ek˝ u kl´ozok ¨osszs´ uly´at maximaliz´alja, azaz X hc χ (c (y1 . . . yn ) = IGAZ) ⇒ max c∈K
Feltessz¨ uk, hogy egyik kl´oz sem tartalmazza ugyanazt a v´altoz´oz neg´alva, ´es nem neg´alva is, azaz minden c kl´ozhoz van olyan igazs´ag´ert´ekel´ese a v´altoz´oknak, amelyben c HAMIS ´ert´eket vesz fel. Vegy¨ uk ´eszere, hogy ekkor minden kl´ozt a benne szerepl˝o v´altoz´ok egyetlen ki´ert´ekel´ese tesz hamiss´a. Pl.: ha c = (x1 ∨ x2 ∨ x¯3 ), akkor a c kl´oz az x1 = HAMIS, x2 = HAMIS, x3 = IGAZ igazs´ag´ert´ekel´esben vesz fel HAMIS ´ert´eket, ezeknek a v´altoz´oknak minden, az el˝obb´ıt˝ol k¨ ul¨onb¨oz˝o ´ert´ekel´es´eben, c IGAZ ´ert´eket vesz fel.
1. Algoritmus Minden c ∈ K kl´ozhoz hozz´arendel¨ unk egy Xc v´eletlen v´altoz´ot, amely az (y1 , . . . , yn ) igazs´ag´ert´ekel´esekhez rendel egy sz´amot: hc , ha c (y1 . . . yn ) = IGAZ; Xc (y1 . . . yn ) = 0, k¨ ul¨onben. Az elemi esem´enyek az {xi = IGAZ}, vagy {xi = HAMIS}, i = 1, . . . , n. Feltessz¨ uk, us´ege, hogy c hogy P ({xi = IGAZ}) = P ({xi = HAMIS}) = 12 . Ekkor annak a val´osz´ın˝ kl´oz IGAZ ´ert´eket vesz fel: P (c = IGAZ) = 1 − P (c = HAMIS) = 1 − 1/2kc , ahol kc a c kl´oz liter´aljainak sz´ama. Teh´at Xc v´arhat´o ´ert´eke E(Xc ) = hc (1 − 2−kc ). Vezess¨ uk be az αk = 1 − 2−k P jel¨ol´est. Legyen X := c∈K Xc . Kihaszn´alva a v´arhat´o ´ert´ek alap tulajdons´agait ad´odik, hogy X X 1X 1 E(X) = E( Xc ) = hc (1 − 2−kc ) ≥ hc ≥ OPT. 2 c∈K 2 c∈K c∈K Teh´at, azon v´eletlen algoritmusn´al, mely n (szab´alyos ´erm´evel t¨ort´en˝o) p´enzfeldob´assal hat´arozza meg az y1 . . . yn igazs´ag´ert´ekel´est, a kiel´eg´ıtett kl´ozok o¨sszs´ ulya v´arhat´oan legal´abb az optimum fele lesz. Ha minden kl´oz legal´abb k´et liter´alb´ol a´ll, akkor kc ≥ 2 (∀c ∈ K), ´es ekkor az algoritmus randomiz´alt 3/4-approxim´aci´o. 1
Derandomiz´ al´ as A derandomiz´al´ashoz haszn´aljuk az al´abbi azonoss´agot: T´ etel: E(X|x1 = a1 , . . . , xi = ai ) = E(X|x1 = a1 , . . . , xi = ai , xi+1 = IGAZ)P (xi+1 = IGAZ) +E(X|x1 = a1 , . . . , xi = ai , xi+1 = HAMIS)P (xi+1 = HAMIS) Ennek egy trivi´alis k¨ovetkezm´enye T´ etel: E(X|x1 = a1 , . . . , xi = ai ) ≤ max [E(X|x1 = a1 , . . . , xi = ai , xi+1 = IGAZ), E(X|x1 = a1 , . . . , xi = ai , xi+1 = HAMIS)] Ezek alapj´an a derandomiz´alt algoritmus: • Kisz´am´ıtjuk az E(X|x1 = IGAZ) ´es az E(X|x1 = HAMIS) ´ert´ekeket, ´es vessz¨ uk a maximumot. • Ez alapj´an r¨ogz´ıtj¨ uk x1 -et. Legyen ez az optimum a1 . • Ha m´ar r¨ogz´ıtett¨ uk az a1 , . . . , ai ´ert´ekeket, akkor ism´etelj¨ uk az elj´ar´ast E(X|x1 = a1 , . . . , xi = ai , xi+1 = IGAZ) ´es E(X|x1 = a1 , . . . , xi = ai , xi+1 = HAMIS) meghat´aroz´as´aval. ´Igy az elj´ar´as v´eg´en kapunk egy a1 , . . . , an sorozatot, melyre teljes¨ ul, hogy: E(X) ≤ E(X|x1 = a1 ) ≤ . . . ≤ E(X|x1 = a1 , . . . , xn = an ), ahol a sorozat utols´o tagja m´ar konstans. Teh´at a derandomiz´al´assal kapunk egy poly idej˝ u determinisztikus 1/2-es approxim´aci´ot (illetve 3/4 approxim´aci´ot, ha minden kl´oz legal´abb 2 liter´alb´ol ´all). P´ elda: H´arom v´altoz´o f¨ol¨ott, x1 , x2 , x3 , tekints¨ uk a k¨ovetkez˝o kl´ozokat: c1 = (x1 ∨ x2 ), c2 = (x1 ∨ x¯2 ), c3 = (¯ x1 ∨ x3 ), melyek s´ ulya hc1 = 1, hc2 = 1, hc3 = 2 + . Mivel minden kl´oz 2 liter´alb´ol a´ll, P (ci = IGAZ) = 43 mindh´arom kl´oz eset´en. K¨ovetkez´esk´eppen E(Xci ) = 43 hci . Teh´at a randomiz´alt algoritmus olyan eredm´enyt ad, melynek v´arhat´o ´ert´eke E(X) = 43 (1 + 1 + (2 + )) = 3 + 43 . Alkalmazzuk a determinisztikus (derandomiz´alt) algoritmust. Ehhez el˝osz¨or is figyelj¨ uk meg, hogy P (c1 = IGAZ|x1 = IGAZ) = 1, P (c2 = IGAZ|x1 = IGAZ) = 1, P (c3 = IGAZ|x1 = IGAZ) = 12 , teh´at E(X|x1 = IGAZ) =
3 X i=1
1 1 1 E(Xci |x1 = IGAZ) = hc1 + hc2 + hc3 = 1 + 1 + (2 + ) = 3 + 2 2 2 2
Tov´abb´a, P (c1 = IGAZ|x1 = HAMIS) = P (c3 = IGAZ|x1 = HAMIS) = 1, ez´ert E(X|x1 = HAMIS) =
3 X i=1
1 , 2
P (c2 = IGAZ|x1 = HAMIS) =
1 , 2
1 1 E(Xci |x1 = HAMIS) = (hc1 +hc2 )+hc3 = (1+1)+(2+) = 3+ 2 2
Teh´az r¨ogz´ıtj¨ uk a x1 = HAMIS igazs´ag´ert´ekel´est. Ekkor azonban m´ar l´enyeg´eben k´esz is vagyunk, az x2 ´es x3 igazs´ag´ert´ekel´ese nem befoly´asolja az eredm´enyt. Mi´ert ? Mivel c3 = IGAZ ha x1 = HAMIS, valamint pontosan az egyik mindig igaz lesz a c1 ´es c2 kl´ozok k¨oz¨ ul, ´es hc1 = hc2 . A kapott igazs´ag´ert´ekel´es teh´at, x1 = HAMIS, valamint x2 ´es x3 tetsz˝oleges r¨ogz´ıt´ese. A teljes¨ ul˝o kl´ozok o¨sszs´ ulya 3 + . Ezzel szemben, az optim´alis megold´as x1 = x3 = IGAZ, x2 tetsz˝oleges. Ekkor minden kl´oz teljes¨ ul, ´es a megold´as s´ ulya 4 + . Teh´at a derandomiz´alt algoritmus eredm´enye = 34 × OP T , ( → 0). Ez a p´elda igazolja, hogy az algoritmus elemz´ese ´eles abban az esetbem, ha minden ul. kl´oz legal´abb k´et liter´alb´ol a´ll, mert ekkor αkc ≥ 3/4 minden c ∈ K kl´ozra teljes¨
2. Algoritmus Egy m´asik megk¨ozel´ıt´es, hogy egy line´aris programmal hat´arozzuk meg a P (xi = IGAZ) val´osz´ın˝ us´eget, i = 1, . . . , n. (Vagyis nem szab´alyos p´enz´erm´evel dobunk.) Adott c kl´ozra legyen c− , illetve c+ a neg´alt, ´es a nem neg´alt v´altoz´ok indexhalmaza c-ben. Pl.: ha c = (x1 ∨ x2 ∨ x¯3 ), akkor c− = {3}, c+ = {1, 2}. A line´aris programban az yi d¨ont´esi v´altoz´o reprezent´alja a P (xi = IGAZ) val´osz´ın˝ us´eget, ´es zc pedig a c kl´oz teljes¨ ul´es´enek a val´osz´ın˝ us´eg´et, ami persze f¨ ugg a benne szerepl˝o v´altoz´ok igazs´ag´ert´ekel´es´et˝ol. Ekkor az LP a k¨ovetkez˝o: P max c∈K hc zc P
i∈c+
P yi + i∈c− (1 − yi ) ≥ zc , 0 ≤ yi ≤ 1 i = 1 . . . n 0 ≤ zc ≤ 1 C ∈ K
c∈K
Legyen (y1∗ , . . . , yn∗ , zc∗1 , . . . , zc∗m ) egy optim´alis megold´asa a fenti line´aris programnak. Az algoritmus a k¨ovetkez˝o: oldjuk meg a line´aris programot, ´es ut´ana hamis p´enzek feldob´as´aval kiv´alasztjuk az xi v´altoz´ok ´ert´ekel´es´et, ahol P (xi = IGAZ) = yi∗ . k Vezess¨ uk be a βk = 1 − 1 − k1 jel¨ol´est. T´ etel: Ha a c kl´oz k liter´altb´ol a´ll, akkor P (c = IGAZ) ≥ βk zc∗ Bizony´ıt´ as: Feltehetj¨ uk, hogy c-ben minden v´altoz´o nem neg´alt, illetve a v´altoz´ok a´tnevez´es´evel c = (x1 ∨. . .∨xk ). Ekkor felhaszn´alva a sz´amtani-m´ertani k¨ozepek k¨oz¨otti egyenl˝otlens´eget,
3
ad´odik, hogy P (c = IGAZ) = 1 −
1−
1−
k Y
i=1 Pk ∗ !k i=1 yi
k
(1 − yi∗ ) ≥ 1 −
Pk
∗ i=1 1 − yi k
!k =
k zc∗ ≥ βk zc∗ . ≥1− 1− k
∗ k Az utols´o egyenl˝otlens´eg g(zc∗ ) = 1− 1 − zkc ≥ βk zc∗ abb´ol k¨ovetkezik, hogy g(z) konk´av, valamint g(0) = 0, g(1) = βk . M´eg szeml´eletesebb, ha a´br´azoljuk a k´et ´ert´eket.
A fenti t´etelb˝ol ad´odik, hogy E(Xc ) ≥ hc βk zc∗ . Felhaszn´alva, hogy βk ≥ 1 − 1e minden k ≥ 1-re: X X 1 X 1 ∗ E(X) = E( Xc ) = E(Xc ) ≥ 1 − hc zc ≥ 1 − OPT. e e c∈K c∈K c∈K ˆ Az el˝obbi algoritmus elemz´ese jav´ıthat´o, ha van egy olyan kˆ korl´at, melyre kc ≤ k, ∀c ∈ K, mert ekkor az algoritmus hib´aja βkˆ ≥ 1 − 1/e. A 2. algoritmus szint´en derandomiz´altah´o, m´egpedig ugyanazzal a m´odszerrel, mint az 1. algoritmus. R´eszletesebben: el˝osz¨or meg kell hat´arozni az E(X|x1 = IGAZ), ´es az E(X|x1 = HAMIS) ´ert´ekeket. Ennek menete: r¨ogz´ıts¨ uk az y1 ´ert´ek´et 1-ra (x1 = IGAZ), illetve 0-re (x1 = HAMIS). A r¨ogz´ıtett y1 mellett sz´amoljuk ki u ´jra az LP optim´alis megold´as´at, ´es az y1 , y2 , . . . , yn v´altoz´ok ´ert´ek´evel defini´aljuk a P (xi = IGAZ) val´osz´ın˝ us´egeket. A kapott val´osz´ın˝ us´egekkel hat´arozzuk meg az E(X|x1 = IGAZ), illetve az E(X|x1 = HAMIS) v´arhat´o´ert´ekeket. A k´et ´ert´ek maximum´at v´alasztva r¨ogz´ıtj¨ uk x1 igazs´ag´ert´ek´et, ´es y1 -et is. Az eg´eszet ism´etelj¨ uk, a r¨ogz´ıtett y1 mellett, az y2 , . . . , yn r¨ogz´ıt´ese ´erdek´eben. Teh´at a derandomiz´al´as eredm´enye egy determinisztikus, polinomi´alis idej˝ u, 1 − 1e approxim´aci´os algoritmus a Max-SAT probl´em´ara.
4
P´ elda: Alkalmazzuk a 2. randomiz´alt algoritmust a k¨ovetkez˝o p´eld´ara. A logikai v´altoz´ok x1 , . . . , xn , amelyek f¨ol¨ott defini´alunk 2n kl´ozt: ! _ cj = xi , hj = n j = 1, . . . , n i6=j cn+j = x¯j , hn+j = 1 A line´aris program: max
n X
n · zj +
j=1
X
2n X
zj
j=n+1
yi ≥ zj ,
j = 1, . . . , n
i6=j
1 − yj ≥ zn+j , 0≤y≤1 0≤z≤1
j = 1, . . . , n
Optim´alis LP megold´as: yi∗ = 1/(n − 1), i = 1, . . . , n, and zj∗ = 1, j = 1, . . . , n, zj = (n − 2)/(n − 1), j = n + 1, . . . , 2n. A P (xi = IGAZ) = yi∗ mellett n−1 ! 1 E(Xcj ) = n 1 − 1 − j = 1, . . . , n. n−1 E(Xcj ) =
n−2 n−1
j = n + 1, . . . , 2n.
Teh´at E(X) = n2
1− 1−
1 n−1
n−1 ! +
n(n − 2) n−1
Egy optim´alis eg´esz megold´as: y¯1 = y¯2 = 1, y¯i = 0, i = 3, . . . , n, z¯j = 1, ha j ∈ {1, . . . , n} ∪ {n + 3, . . . , 2n}, z¯n+1 = z¯n+2 = 0. Az eg´esz megold´as ´ert´eke: OP TIP = n2 + n − 2. Ha E(X) n → ∞, akkor OP → 1 − 1e . TIP A derandomiz´alt algoritmus eredm´enye egy optim´alis eg´esz megold´as lesz, de persze ez csak a ”v´eletlen m˝ uve”.
Kombin´ alt Algoritmus Az el˝oz˝o k´et algoritmust kombin´al´as´aval egy mindkett˝on´el jobb elj´ar´ast kaphatunk. Legyen b ∈ {0, 1} v´eletlen v´altoz´o, P (b = 1) = P (b = 0) = 1/2 val´osz´ın˝ us´egekkel. Ha b = 0, az 1. algoritmust alkalmazzuk, ha b = 1, a 2. algoritmust haszn´aljuk. Legyen (y1∗ , . . . , yn∗ , zc∗1 , . . . , zc∗m ) az optim´alis megold´asa a 2. algoritmusban felhaszn´alt line´aris programnak. Ekkor 5
T´ etel:
3 P (c = IGAZ) = zc∗ 4
Bizony´ıt´ as: Az {xi = IGAZ} elemi esem´enyek val´osz´ın˝ us´eg´et felt´etelesen defini´aljuk a b = 0, illetve b = 1 felt´etelek mellett. Ha b = 0, akkor P (xi = IGAZ) = 12 (az els˝o m´odszer szerint), m´ıg ha b = 1, akkor P (xi = IGAZ) = yi∗ . Ebb˝ol k¨ovetkezik, hogy • P (c = IGAZ|b = 0) = αk ≥ αk zc∗ • P (c = IGAZ|b = 1) ≥ βk zc∗ Teh´at 1 1 (αk + βk )zc∗ 3 P (c = IGAZ) = P (c = IGAZ|b = 0) + P (c = IGAZ|b = 1) = ≥ zc∗ 2 2 2 4 Megjegyz´ es: Az
(αk +βk )zc∗ 2
≥ 34 zc∗ egyenl˝otlens´eg az αk + βk ≥
3 2
o¨sszef¨ ugg´esb˝ol ad´odik.
A fenti t´etelt f¨olhaszn´alva kapjuk, hogy E(Xc ) ≥ 34 hc zc∗ . Ezek alapj´an ad´odik, hogy E(X) =
X
E(Xc ) ≥
c∈K
3X 3 hc zc∗ ≥ OPT. 4 c∈K 4
Derandomiz´ al´ as A kombin´alt algoritmus, az 1. algoritmitmushoz hasonl´oan derandomiz´alhat´o: Determinisztikus 3/4 approx algoritmus a Max-SAT probl´em´ara 1. Alkalmazzuk a determinisztikus 1/2 approxim´aci´os algoritmust, a kapott igazs´ag´ert´ekel´es legyen m1 . 2. Alkalmazzuk a determinisztikus 1−1/e approxim´aci´os algoritmust, a kapott igazs´ag´ert´ekel´es legyen m2 . 3. Adjuk vissza a nagyobb ´ert´ek˝ u eredm´enyt ad´ot az m1 ´es m2 igazs´ag´ert´ekel´esek k¨oz¨ ul. T´ etel: A kombin´alt algoritmus Biz.
3 4
approxim´aci´o a Max-SAT probl´em´ara.
1 E(X) = E(X|b = 0)P (b = 0) + E(X|b = 1)P (b = 1) = (E(X|b = 0) + E(X|b = 1)). 2 Teh´at, E(X) ≤ max{E(X|b = 0), E(X|b = 1)}. 6
Mivel E(X) ≥
3 4
× OP T , az egyik algoritmus eredm´enye legal´abb
3 4
× OP T .
P´ elda: A m´asodik algoritmus ut´ani p´eld´ara alkalmazzva a kombin´alt algoritmust optim´alis megold´ast kapunk, hiszen a derandomiz´alt (1 − 1e )-approxim´aci´os algoritmus azon a feladaton megtal´alja az optim´alis megold´ast.
7
10. elõadás 2012.03.09. Leírta: Dudás László 1.
A Hátizsák feladat
Feladat: : Van n db csomagunk az i. csomag pro tja, hasznossága pi , a mérete pedig aj > 0. Van egy B méretû hátizsákunk(feltesszük, hogy aj < B∀j , különben kidobjuk). S
meg szeretnénk pakolni a hátizsákot úgy, hogy a benne található tárgyak összértéke maximállis legyen. S ⊆ {1, . . . , n} X
aj ≤ B
j∈S
X
pj → max
j∈S
IP: max
n X
p j xj
j=1 n X
aj x j ≤ B
j=1
xj ∈ {0, 1} 1 j∈S xj = 0 j∈ /S
Az LP relaxált: max
X
p j xj
j∈S n X
aj x j ≤ B
j=1
0 ≤ xj ≤ 1 ∀j
1
Feltehetõ, hogy ap11 ≥ ap22 ≥ · · · ≥ apnn . Állítás: P Az LP relaxált optimális megoldása: Ha nj=1 aj ≤ B ⇒ x1 = · · · = xn = 1 optimális megoldása LP relaxáltnak és az IP-nek is. P P B PKB +1 Ha nj=1 aj > B ⇒ ∃KB : K aj j=1 aj ≤ B < j=1 x1 = 1, . . . , xKB = 1, xKB +1 =
relaxáltnak.
PKB B− j=1 aj , xKB +2 aKB +1
= 0, . . . , xn = 0 optimális megoldása a
Bizonyítás: Az állítás elsõ része triviális, a második része pedig következik abból, hogy
a hátizsák be van töltve a lehetõ legjobb. P B +1egészen és a fajlagos P értéke B +1 Következmény: Kj=1 pj > OPT ,mert K p j > LPOPT ≥ OPT j=1
Algoritmus (a) Ha
P
j=1
n ≤ B ⇒ OPT mo.: x1 = · · · = xn = 1, Állj!
(b) Különben LB1 =
KB X
pj
j=1
LB2 = pKB +1
(c) Ha LB1 > LB2 , eredmény: x1 = · · · = xKB , xi = 0 i ≥ KB + 1 Különben XKB +1 = 1 xi = 0 ∀i 6= KB + 1
Állítás: max(LB1 , LB2 ) ≥ OPT 2 Bizonyítás: Tegyük fel indirekt, hogy max(LB1 , LB2 ) < ⇒ OPT > LB1 + LB2 =
KX B +1
OPT 2
pj > LPOPT ≥ OPT
j=1
Kijött az ellentmondás. Következmény: az algoritmus Ha
n X
1 2
approximáció.
aj ≤ B ⇒ OPT megoldást ad.
1
Ha
n X
aj > B ⇒ az el®z® állítás miatt.
1
De níció: Teljesen polinomiális idej¶ approximációs séma (TPIAS) (angolul FPTAS)
Adott egy M optimalizálási feladat és egy hiba korlát. Ha M maximalizációs feladat, akkor egy TPIAS olyan eredményt ad, melynek célfüggvény értéke ≥ (1 − )OPT. Ha M mininmalizációs feladat, akkor egy TPIAS olyan eredményt ad, melynek célfüggvény 2
értéke ≤ (1 + )OPT. Mindkét esetben a futási idõ polinomiális az input hosszában és 1 -ban.
De níció: Legyen M ax[I] az I feladatpéldányban el®forduló legnagyobb abszolutér-
ték.
De níció: Pseudopolinomiális algoritmus: polinomiális idej¶ a feladat hosszában és
M ax[I]-ben.
1.1.
Pseudo polinomiális algoritmus a hátizsák fealadatra(dinamikus programozás)
Algoritmus: (a) A(0, p) = 0 ∀p = 0 . . . n · pmax pmax = maxj pj (b) A(i, p) = mérete a legkisebb összméret¶ halmaznak az 1 . . . i elemek közül, ami p pro tot ér el =
min(A(i − 1, p), ai + A(i − 1, p − pi )) A(i − 1, p)
ha pi ≤ p ha pi > p
∀p = 0 . . . n · pmax
Állítás: A hátizsák feladat optimuma max(p : A(n, P ) ≤ B) (Bizonyítás: ) következik a de nícióból(megoldás is visszakereshetõ). Futási idõ:O(n2 pmax ) ⇒ Pszeudopolinomiális, ha pmax ≤ q(n) q polinom ⇒ polinomiális
1.2.
TPIAS a hátizsák feladatra(I, )
(a) K =
·pmax n
(b) p0j =
pj K
(c) Alkalmazzuk a dinamikus programot a (n, p0 , a, B) inputra: S 0 az optimális megoldás (d) Eredmény: S 0
Állítás: Legyen S 0 a TPIAS megoldása. Ekkor P (S 0 ) ≥ (1 − )OPT Bizonyítás: X p(S 0 ) =
pj
j∈S 0
Legyen O a hátizsák feladat egy optimális megoldása. Ekkor K · p0 (O) ≥ p(O) − nK , mert 3
kerekítésbõl: K · p0j ≥ pj − K . p(S 0 ) ≥ K · p0 (S 0 ) ≥ K · p0 (O) ≥ p(O) − nK = p(O) −
npmax ≥ (1 − )OPT n
Ezzel az állítást beláttuk. Futási id®: a dinamikus program határozza meg (a többi lépés lineáris). A dinamikus prog2 3 ram futási ideje O(n2 p0max ) = O( n pKmax ) = O( n ) ⇒ polinomiális n-ben és 1 -ban ⇒ TPIAS.
De níció: Π döntési probléma er®sen NP-nehéz, ha van olyan p polinom, hogy a M ax[I] ≤ p(|I|) feltételt teljesít® I ∈ Π feladatpéldányokból álló részfeladat NP-nehéz. Állítás: Ha P 6= NP, akkor egyetlen Π er®sen NP-nehéz problémára sincs pszeudo-
polinomiális algoritmus. Bizonyítás: Legyen Π erõsen NP-nehéz pobléma. Ekkor de níció szerint van egy p polinom, amellyel korlátozva a feladatpélányokban el®forduló maximális számokat, NPnehéz problémát kapunk. Ezek után ha Π megoldható pseudo-polinomiális id®ben, akkor a részprobléma minden I feladatpéldánya megoldható polinomiális id®ben I hosszában, és M ax[I]-ben. Utóbbi azonban legfeljebb p(|I|), tehát egy NP-nehéz részprobléma polinomiális id®ben oldható meg. Ellentmondás. Állítás: Legyen Π egy NP-nehéz optimalizálási feladat, melynek optimumértéke mindig egész szám, p kétváltozós polinom, melyre OPT(I) < p(|I|, M ax[I]) ∀I ∈ Π. Ekkor ha van egy TPIAS a Π-re, akkor a Π pszeudopolinomiális idõben megoldható. Bizonyítás: Legyen A egy TPIAS Π-re, q(|I| , 1 ) futásid®vel, ahol > 0 a megengedett hiba. Legyen I tetsz®leges példányaa Π-nek, és = 1/p(|I|, M ax[I]). Alkalmazzuk az A algoritmust az I -re!
OP T (I) ≤ A(I) ≤ (1 + )OPT(I) = OPT(I) + · OPT(I) < OPT(I) + · p(|I|, M ax[I]) = OPT(I) + 1 ⇒ A(I) = OPT(I) Futási id®: q(|I| , 1 ), ahol q polinom. Tehát polinomiális I hosszában, mivel = 1/p(|I|, M ax[I]) Következmény: Ha P 6= NP, és Π erõsen NP-nehéz és teljesülnek rá az elõzõ állítás feltételei, akkor nincs TPIAS Π-res. Bizonyítás: Tegyük fel, hogy ∃Π-re TPIAS ⇒ pszeudo polinomiális algoritmus Π-re. Ugyanakkor erõsen NP-nehéz problémára nem létezik pszeudo polinomiális algoritmus.
Ellentmondás.
4
11. El˝ oad´ as, 2013. 05. 17. V´ eletlent haszn´ al´ o algoritmus a t¨ obbsz¨ or¨ os v´ ag´ as probl´ em´ ara Adott egy G = (V, E) egyszer˝ u ir´any´ıtatlan gr´af, c : E → R+ s´ ulyf¨ uggv´eny az ´eleken, ´es k darab k¨ ul¨onb¨oz˝o cs´ ucs, s1 , . . . , sk ∈ V , a gr´afb´ol. Keress¨ uk egy olyan k partici´oj´at a cs´ ucsoknak, V = V1 ∪· · ·∪Vk , hogy si ∈ Vi , i = 1, . . . , k, ´es azoknak az ´eleknek az o¨sszs´ ulya, emelyek v´egpontjai k¨ ul¨onb¨oz˝o Vi halmazokba esenkek, a lehet˝o legkisebb. Erre m´ar l´attunk egy 2 − 2/k approxim´aci´os algoritmust. Most mutatunk egy olyan v´eletlent haszn´al´o algoritmust, ami v´arhat´o ´ert´ekben olyan megold´ast ad, ami az optimumnak legfeljebb 1.5−1/k szorosa. IP probl´ ema: min
X
c(u, v)d(u, v)
(1)
(u,v)∈E
felt´etelek k
1X i d(u, v) = |x − xiv |, 2 i=1 u k X
xiu = 1,
(u, v) ∈ E
(2)
u∈V
(3)
i = 1, . . . , k
(4)
i=1
xs i = e i ,
xv ∈ {0, 1}k ,
v∈V
(5)
Az eg´esz megold´asban minden xv v´altoz´o vektor pontosan egy koordin´at´aja 1-es, a t¨obbi 0, az (3) felt´etel, ´es az xv eg´esz´ert´ek˝ us´ege miatt. Ebb˝ol k¨ovetkezik, hogy d(u, v) = 0 vagy 1, att´ol f¨ ugg˝oen, hogy xu ´es xv azonos koordin´at´aja 1-es ´ert´ek˝ u, vagy nem. Teh´at az eg´esz v´altoz´os program optimuma ´eppen a v´ag´asi probl´ema optimum´at adja. A felt´etelek lineariz´alhat´oak u ´j v´altoz´ok bevezet´es´evel:
1
LP probl´ ema: X
min
c(u, v)d(u, v)
(6)
(u,v)∈E
felt´etelek k
1X i d(u, v) = x , 2 i=1 uv
(u, v) ∈ E
(7)
xiuv ≥ xiu − xiv ,
(u, v) ∈ E
(8)
xiuv
(u, v) ∈ E
(9)
k X
≥
xiv
−
xiu = 1,
xiu ,
u∈V
(10)
i = 1, . . . , k
(11)
i=1
xs i = e i ,
0 ≤ xiv ≤ 1,
v ∈ V, i = 1, . . . , k
(12)
Mivel c(u, v) ≥ 0, egy optim´alis megold´asban xiuv = |xiu − xiv |. ´ cs´ Lemma: Uj ucsok hozz´av´etel´evel a gr´afhoz feltehet˝o, hogy az LP optim´alis megold´as´aban minden (u, v) ∈ E ´elre, xu , ´es xv legfeljebb 2 koordin´at´aban k¨ ul¨onb¨ozik. P Mivel ki=1 xiu = 1, ez´ert xu ´es xv vagy egyenl˝o, vagy pontosan k´et koordin´at´aban t´er el, r´aad´asul ha i, ´es j ez a k´et koordin´ata, ´es mondjuk xiu < xiv , akkor xiv − xiu = xju − xjv = d(u, v). Adott egy x optim´alis megold´asa az LP relax´aci´onak. Legyen Ei = {(u, v) ∈ E | xiu 6= Minden e ∈ E, amelyre d(e) > 0, pontosan k´et halmazhoz fog tartozni az el˝obbi lemma miatt. P Legyen Wi = e∈Ei c(e)d(e), ´es tegy¨ uk fel, hogy Wk ≥ Wi (sz¨ uks´eg eset´en ´atsorsz´amozzuk az si cs´ ucsokat). Adott ρ ∈ (0, 1) ´ert´ekhez defini´aljuk a xiv }.
B(si , ρ) = {v ∈ V | xiv ≥ ρ} halmazt. A k¨ovetkez˝o algoritmusban ρ egy egyenletes eloszl´as´ u v´eletlen v´altoz´o, ´es σ egy 1 1 olyan v´eletlen v´altoz´o, ami 2 − 2 val´osz´ın˝ us´eggel jel¨oli (v´alasztja ´ert´ek¨ ul) az (1, 2, . . . , k − 1, k), ´es a (k − 1, k − 2, . . . , 1, k) permut´aci´ok egyik´et. Azt mondjuk, hogy j <σ i, ha j megel˝ozi i-t a σ permut´aci´oban. Az algoritmus l´ep´esei: 1) Megoldjuk az LP-t, legyen x az optim´alis megold´as. 2) Sz¨ uks´eg eset´en ´atsorsz´amozunk, hogy Wk ≥ Wi teljes¨ ulj¨on minden i = 1, . . . , k − 1-re. 3) V´alasszunk egy v´eletlen ρ ∈ (0, 1) ´ert´eket, ´es egy σ ∈ {(1, 2, . . . , k − 1, k), (k − 1, k − 2, . . . , 1, k)} permut´aci´ot. 2
4) Legyen Vσ(i) = B(sσ(i) , ρ) \ S 5) Vk = V \ j
S
j
Vσ(j) . i = 1, . . . , k − 1.
6) Eredm´eny: C := {(u, v) | ∃i 6= j : u ∈ Vi , v ∈ Vj }. Az algoritmus elemz´es´ehez bel´atjuk a k¨ovetkez˝ot: Lemma: Ha e ∈ E \ Ek , akkor P r(e ∈ C) ≤ 1.5d(e), m´ıg ha e ∈ Ek , alkkor P r(e ∈ C) ≤ d(e). Bizony´ıt´ as: El˝osz¨or legyen (u, v) ∈ E \ Ek . Tegy¨ uk fel, hogy xiu < xiv . Ekkor xjv < xju . Tegy¨ uk fel, hogy xiu ≤ xjv (hasonl´o a bizony´ıt´as, ha xjv ≤ xiu ). Ekkor van k´et egyforma hossz´ u intervallumunk: IL := (xiu , xiv ], ´es IR := (xjv , xju ]. A k´et intervallum lehet diszjunkt, de egym´asba is metszhetnek, de xiu ≤ xjv miatt IL ”balra” helyezkedik el IR -t˝ol. Figyelj¨ uk meg, hogy u illetve v a Vi , Vj , Vk halamzok k¨oz¨ ul pontosan az egyikbe ker¨ ul, ´es csak akkor lesznek elv´alasztva, ha vagy a Vi meghat´aroz´asakor u ´es v m´eg nincs elv´alasztva, ´es ρ ∈ IL , vagy a Vj meghat´aroz´asakor u ´es v m´eg nincs elv´alasztva, ´es ρ ∈ IR . El˝osz¨or vizsg´aljuk azt az esetet, amikor az algoritmus azt a permut´aci´ot v´alasztja, melyben i ≺σ j. Csak akkor lesz u ´es v elv´alasztva, ha ρ ∈ IL ´es ekkor i feldolgoz´asa sor´an v beker¨ ul Vi halmazba, de u nem; vagy ρ ∈ IR \ IL , ´es ekkor j feldolgoz´asa sor´an u beker¨ ul a Vj halmazba, de v nem. A fenti k´et esem´eny val´osz´ın˝ us´ege legfeljebb P r(ρ ∈ IL ∪ IR ) ≤ 2d(u, v). Most tekints¨ uk azt az esetet, amikor j ≺σ i. Csak akkor lesz u ´es v elv´alasztva, ha ρ ∈ IR , aminek a val´osz´ın˝ us´ege P r(ρ ∈ IR ), ugyanis ha ρ ∈ IR , akkor j feldolgoz´asa sor´an u beker¨ ul a Vj halmazba, de v nem; ha pedig ρ ∈ IL \ IR , akkor a j feldolgoz´asa sor´an mindk´et cs´ ucs beker¨ ul a Vj jalmazba. ¨ Osszegezve, ha (u, v) ∈ E \ Ek , akkor 1 1 P r((u, v) ∈ C) ≤ P r(ρ ∈ IL ∪ IR ) + P r(ρ ∈ IR ). ≤ 1.5d(u, v) 2 2 Ha (u, v) ∈ Ek , legyen Ei a m´asik halmaz, ami tartalmazza az (u, v) ´elet. u ´es v csak u ´gy ker¨ ulhetnek k¨ ul¨onb¨oz˝o halmazokba, ha egyik¨ uk Vi -be ker¨ ul, a m´asik nem, aminek a val´osz´ın˝ us´ege P r(ρ ∈ IL ) = d(u, v). T´ etel: V´arhat´o ´ert´ekben az algoritmus eredm´enye: P E[c(C)] ≤ (1.5 − 1/k)OPTLP . Bizony´ıt´ as: C t¨obbsz¨or¨os v´ag´as. OPTLP = e∈E c(e)d(e). Mivel d(e) > 0 eset´en P e pontosan k´et Ei halmazba esik, ez´ert ki=1 Wi = 2OPTLP . Mivel Wk a legnagyobb a W1 , . . . , Wk k¨oz¨ ul, Wk ≥ k2 OPTLP . X X X E[c(C)] = c(e)P r(e ∈ C) = c(e)P r(e ∈ C) + c(e)P r(e ∈ C) (13) e∈E
≤ 1.5
e∈E−Ek
X
c(e)d(e) − 0.5
e∈E
X
e∈Ek
c(e)d(e) = 1.5OPTLP − 0.5Wk
(14)
e∈Ek
≤ (1.5 − 1/k)OPTLP .
(15)
3
