Approksimointialgoritmit (kev¨ at 2010) Harjoitus 1 (25. tammikuuta)
Ratkaisuja (Jouni Siren)
1. OlkootSjaS0 verkon maksimaalisia pariutuksia. Tarkastellaan kaarta (u, v)∈S0. Pariutuk- sessaS voi olla korkeintaan yksi kaari, jolla on p¨a¨atepisteen¨a solmu u, ja korkeintaan yksi kaari, jolla on p¨a¨atepisteen¨a solmuv. Jokaista pariutuksenS0 kaarta vastaa siis korkeintaan kaksi pariutuksenS kaarta. Toisaalta jokaisen pariutuksenS kaarene t¨aytyy koskettaa jo- tain pariutuksenS0 kaarta, sill¨a muutenS0∪ {e} olisi pariutus eik¨a S0 olisi maksimaalinen.
N¨ain ollen|S| ≤2· |S0|.
OlkoonSA on ahneen algoritmin l¨oyt¨am¨a maksimaalinen pariutus ja SOPT lukum¨a¨ar¨aisesti pienin maksimaalinen pariutus. KoskaSA ≤2· |SOPT|, on ahne algoritmi 2-approksimointi- algoritmi lukum¨a¨ar¨aisesti pienimm¨an maksimaalisen pariutuksen l¨oyt¨amiseen.
2. OlkoonT verkonGsyvyyssuuntainen viritt¨av¨a puu jaS sen sis¨asolmujen joukko. Oletetaan, ett¨a verkossa olisi kaari lehtisolmujen u ja v v¨alill¨a. Koska u(v) on lehtisolmu, t¨aytyy sy- vyyssuuntaisen l¨apik¨aynnin k¨ayd¨a kaikissa sen naapureissa ennen sit¨a. T¨am¨a ei kuitenkaan ole mahdollista, sill¨a uja vovat toistensa naapureita. Kaikissa kaarissa ainakin toisen p¨a¨an t¨aytyy siis olla puunT sis¨asolmu, jotenS on verkonGsolmupeite.
Muodostetaan puussaTahne pariutus tekem¨all¨a syvyyssuuntainen l¨apik¨aynti ja pariuttamal- la kukin viel¨a pariton sis¨asolmu ensimm¨aisen lapsensa kanssa. Koska jokainen kaari peitt¨a¨a korkeintaan kaksi sis¨asolmua, saadaan n¨ain pariutus, jossa on ainakind|S|/2ekaarta.
Edellisen perusteella verkon G maksimipariutuksessa on ainakin d|S|/2ekaarta, joten pie- nimm¨ass¨a solmupeitteess¨a t¨aytyy my¨os olla v¨ahint¨a¨and|S|/2esolmua. N¨ain ollen joukon S tulostava algoritmi on 2-approksimointialgoritmi solmupeiteongelmaan.
3. Olkoot Π1ja Π2NP-minimointiongelmia ja (f, g) approksimointisuhteen s¨ailytt¨av¨a palautus ongelmasta Π1 ongelmaan Π2. Oletetaan, ett¨a A on α-approksimointialgoritmi ongelmaan Π2, ja tarkastellaan algoritmiaI7→g(I, A(f(I))).
Tarkastellaan ongelman Π1 tapausta I. Palautuksen m¨a¨aritelm¨an (luentokalvojen sivu 23) mukaisesti
objΠ1(I, g(I, A(f(I))))≤objΠ2(f(I), A(f(I)))≤α·OPTΠ2(f(I))≤α·OPTΠ1(I), jotenI7→g(I, A(f(I))) onα-approksimointialgoritmi ongelmaan Π1. Approksimointisuhteen s¨ailytt¨av¨a palautus s¨ailytt¨a¨a siis approksimointisuhteen.
4. OlkoonG= (V, E) verkko, v ∈V solmu jaUv ⊆V solmun v naapureiden joukko. Joukko C⊆V on klikki, jos (a, b)∈Ekaikillaa, b∈C. Tarkastellaan klikkiongelmaa, jossa pyrit¨a¨an l¨oyt¨am¨a¨an verkonGsuurin klikki, ja osoitetaan se itsepalautuvaksi.
VerkonG atomeita ovat sen solmut, joten ongelman rakeisuus on vaadittu O(log|G|). Pa- lautuksen muodostavat funktiot A(G, v) = Gv = (Uv, E ∩Uv2), f(G, v, C) = C ∪ {v} ja g(G, v, r) =r+ 1. Osoitetaan, ett¨a luentokalvojen sivuilla 29–30 olevat ehdot t¨ayttyv¨at n¨aill¨a funktioilla.
• Koska |Gv|<|G|, ehto 1 t¨ayttyy.
• Solmun v kanssa yhteensopivia ratkaisuita ovat ne verkon G klikit, jotka sis¨alt¨av¨at solmun v. Funktiof on selv¨asti ehdon 2 mukainen bijektio verkonGv klikeilt¨a solmun v sis¨alt¨aville verkonGklikeille.
• Olkoot C10 ja C20 kaksi verkon Gv klikki¨a,C1=f(G, v, C10) jaC2 =f(G, v, C20). Koska obj(G, Ci) = obj(Gv, Ci0) + 1, kun i = 1,2, s¨ailytt¨a¨a funktio f ratkaisuiden C10 ja C20 keskin¨aisen paremmuuden ehdon 3 mukaisesti.
• Jos verkonGv suurimmassa klikiss¨a onrsolmua, niin verkonGsuurimmassa solmunv kanssa yhteensopivassa klikiss¨a on ehdon 4 mukaisestig(G, v, r) =r+ 1 solmua.
Koska funktiotA,f jagovat selv¨asti polynomiaikaisia, on klikkiongelma itsepalautuva.
