Approksimointialgoritmit (kev¨ at 2010) Harjoitus 7 (22. maaliskuuta)

Approksimointialgoritmit (kev¨ at 2010) Harjoitus 7 (22. maaliskuuta)

Ratkaisuja (Jouni Siren)

1. Luennoilla (sivut 228–229) esitetyn mukaisesti l¨oysenn¨oksen ratkaisuun kuuluu kaikilla sol- muillav∈V vektorixv= (xⁱ_v, x^j_v, x^k_v), jonka komponenttien summa on 1. Kukin verkon kaari (u, v)∈E lis¨a¨a optimiratkaisun painoonc(u, v)·d(u, v), miss¨a c(u, v) on kaaren paino ja

d(u, v) =1

2(|xⁱ_u−xⁱ_v|+|x^j_u−x^j_v|+|x^k_u−x^k_v|).

Luentojen perusteella (sivut 231–234) voidaan lis¨aksi olettaa, ett¨a vektoritxujaxv joko ovat identtisi¨a tai eroavat toisistaan t¨asm¨alleen kahden komponentin osalta.

Huom! Jatkossa x^j viittaa vektorin x toiseen komponenttiin permutaation j¨alkeen ja x² toiseen komponenttiin ennen permutaatiota.

Tarkastellaan kaarta (u, v), jolla x_u 6=x_v (muut kaaret eiv¨at vaikuta l¨oysenn¨oksen optimi- ratkaisun eiv¨atk¨a algoritmin tuottaman py¨oristyksen painoon). Oletetaan, ett¨a solmut on nimetty niin, ett¨a xu≥xv. Oletetaan lis¨aksi, ett¨ax¹_u=x¹_v. Nyt

d(u, v) =|x²_u−x²_v|=|x³_u−x³_v|.

Tarkastellaan lukujen 1, 2 ja 3 permutaatioita (i, j, k) ja m¨a¨aritet¨a¨an todenn¨ak¨oisyydet, joilla solmutujavp¨a¨atyv¨at eri joukkoihin. Kaari (u, v) tulee t¨all¨oin osaksi leikkausta ja sen paino vaikuttaa py¨orist¨am¨all¨a saadun ratkaisun kokonaispainoon.

(a) (1,2,3): Jos toinen solmuistaujavkuuluu joukkoonVi, molemmat kuuluvat, sill¨ax¹_u= x¹_v. Kumpikaan ei kuulu siihen todenn¨ak¨oisyydell¨a (1−x¹_u). Koskad(u, v) =x²_u−x²_v >0, p¨a¨ateeu∈V_j jav∈V_k todenn¨ak¨oisyydell¨a (1−x¹_u)·d(u, v)/2.

(b) (1,3,2): Kuten edellinen tapaus.

(c) (2,1,3): Todenn¨ak¨oisyydell¨a d(u, v) p¨ateeu∈V_i jav 6∈ V_i. P¨ainvastainen ei ole mah- dollista, koska x²_u≥x²_v. Todenn¨ak¨oisyydell¨a (1−x²_u) kumpikaan ei kuulu joukkoonV_i. Koska d(u, v) = x²_u−x²_v >0 ja x¹_u =x¹_v, p¨ateeu ∈Vj ja v ∈ Vk todenn¨ak¨oisyydell¨a (1−x²_u)·d(u, v). Yhteistodenn¨ak¨oisyys on siis (2−x²_u)·d(u, v).

(d) (3,1,2): Kuten edellinen tapaus, mutta todenn¨ak¨oisyys on (2−x³_u)·d(u, v).

(e) (2,3,1): Nyt tiedet¨a¨an, ett¨a x²_u > x²_v ja x³_u < x³_v. Solmutu jav saadaan siis eri jouk- koihin, jos u∈Vi jav6∈Vi taiu∈Vj jav∈Vk. Edellisen todenn¨ak¨oisyys on d(u, v) ja j¨alkimm¨aisen (1−x²_u)·d(u, v)/2, joten yhteistodenn¨ak¨oisyys on (3−x²_u)·d(u, v)/2.

(f) (3,2,1): Kuten edellinen tapaus, mutta suuruuserot ovat p¨ainvastaiset ja yhteistoden- n¨ak¨oisyys (3−x³_u)·d(u, v)/2.

Jokainen permutaatioista on yht¨a todenn¨ak¨oinen. Todenn¨ak¨oisyys sille, ett¨a solmut uja v p¨a¨atyv¨at eri joukkoihin, on siis

d(u, v)

6 ·

8−2x¹_u+ 3x²_u+ 3x³_u 2

=7

6 ·d(u, v)−x²_u+x³_u

12 ·d(u, v)≤ 7

6·d(u, v), sill¨a x¹_u +x²_u+x³_u = 1. Kaaren (u, v) vaikutus py¨oristyksen kokonaispainoon on siis odo- tusarvoisesti korkeintaan 7/6 ·c(u, v)·d(u, v), joten leikkauksen C kustannukseksi tulee c(C)≤7/6·OPTf ≤7/6·OPT.

On kuitenkin syyt¨a huomata, ettei algoritmi v¨altt¨am¨att¨a tuota sellaisenaan k¨ayp¨a¨a ratkaisua.

P¨a¨atesolmuistas_ip¨a¨atyy kyll¨a joukkoonV_ijas_kjoukkoonV_k. Sen sijaans_jp¨a¨atyy joukkoon V_j vain todenn¨ak¨oisyydell¨a 1/2; muussa tapauksessa se p¨a¨atyy joukkoonV_k.

Ongelma voidaan korjata vaihtamalla joukon V_j valintakriteeriksi xⁱ_v/2 +x^j_v ≥ ρ₂, jolloin jokainen p¨a¨atesolmu valitaan oikeaan joukkoon. T¨am¨a vaikuttaa todenn¨ak¨oisyyksiin seuraa- vasti.

(a) (1−x¹_u)·d(u, v) (b) (1−x¹_u)·d(u, v)

(c) (3−x²_u)·d(u, v)/2 (d) (3−x³_u)·d(u, v)/2 (e) (3−x²_u)·d(u, v)/2 (f) (3−x³_u)·d(u, v)/2

Yhteistodenn¨ak¨oisyydeksi tulee nyt d(u, v)

6 ·

8−4x¹_u+ 2x²_u+ 2x³_u 2

= 7

6·d(u, v)−x¹_u

6 ·d(u, v)≤7

6 ·d(u, v).

2. Luennoilla (sivu 224) esitetty algoritmi monensuuntaiseen leikkaukseen yleistyy luonnollisella tavalla monensuuntaiseen solmuleikkaukseen: etsit¨a¨an jokaiselle p¨a¨atesolmulle pienin erist¨a- v¨a solmujoukko, pudotetaan painavin n¨aist¨a pois ja valitaan leikkaukseksi yhdiste muista erist¨avist¨a joukoista.

Tarkastellaank-sakaraista t¨ahtiverkkoa ja valitaan sakaroiden k¨arjiss¨a olevat solmutsi p¨a¨a- tesolmuiksi. Asetetaan keskimm¨aisen solmunupainoksic(u) = 1 +εjollainε >0. Lis¨at¨a¨an jokaista p¨a¨atesolmuasi kohti uusi solmuvi, jonka painoksi tuleec(vi) = 1. Korvataan kukin kaari (si, u) kaarilla (si, vi) ja (vi, u).

Algoritmi l¨oyt¨a¨a jokaiselle p¨a¨atesolmulle s_i pienimm¨an erist¨av¨an solmujoukon {vi} ja va- litsee leikkaukseen k−1 t¨allaista joukkoa. Leikkauksen kokonaispainoksi tulee siis k−1.

Toisaalta keskisolmuumuodostaa yksin leikkauksen, jonka paino on 1 +ε, joten algoritmin approksimointisuhde ei voi olla parempi kuink−1.

Esimerkki on tiukka. Olkoon p¨a¨atesolmuas_i vastaava erist¨av¨a joukkoC_i ja sen painoc(C_i).

Koska jokainen monensuuntainen solmuleikkaus on my¨os solmun si erist¨av¨a joukko, p¨atee c(Ci) ≤ OPT. Koska leikkaukseen C valitaan k−1 erist¨av¨a¨a joukkoa, p¨atee sille c(C) ≤ (k−1)·OPT.

3. Tarkastellaan monensuuntaista solmuleikkausta vastaavaa kokonaislukuohjelmaa (luentojen sivu 246) ja sen l¨oysenn¨oksen duaalia (luentojen sivu 248) edellisen teht¨av¨an ratkaisun mu- kaisessa verkossa. Asetetaan kuitenkin keskisolmunupainoksi (kapasiteetiksi) c(u) =k.

Verkon maksimivuo saadaan esimerkiksi viem¨all¨a puolen yksik¨on verran vuota solmusta si

solmuunsi+1kaikillai < ksek¨a solmustask solmuuns1. T¨allainen vuo on maksimivuo, sill¨a se kyll¨ast¨a¨a kaikki verkon ei-p¨a¨atesolmut paitsi keskisolmun. Kokonaisvuoksi tulee k/2.

Kaikilla i 6= j verkossa on polku s_i → v_i → u → v_j → s_j, joten mihin tahansa monen- suuntaiseen solmuleikkaukseen t¨aytyy kuulua keskisolmuutaik−1 kappaletta solmuistav_i. Leikkauksen kokonaispainoksi tulee siis v¨ahint¨a¨an k−1, mik¨a on 2−2/k kertaa enemm¨an kuin verkon maksimivuo.

4. (a) Muodostetaan approksimointisuhteen s¨ailytt¨av¨a palautus monensuuntaisesta leikkauk- sesta osajoukkotakaisinkytkent¨aongelmaan kaarille. Palautus tapahtuu lis¨a¨am¨all¨a verk- koon uusi solmu s, josta tulee verkon ainoa kiinnostava solmu. Lis¨aksi verkkoon tulee kaikilla ikaari (s, si), jonka painoksi tulee∞.

Olkoot si 6=sj kaksi p¨a¨atesolmua. Jokaista alkuper¨aisen verkon polkuasi ;sj vastaa uuden verkon kiinnostava sykli si ;sj →s→si, ja p¨ainvastoin. Jokainen alkuper¨ai- sen verkon monensuuntainen leikkaus on siis k¨ayp¨a ratkaisu osajoukkotakaisinkytken- t¨aongelmaan uudessa verkossa. Vastaavasti jokainen painoltaan ¨a¨arellinen osajoukko- takaisinkytkent¨aongelman k¨ayp¨a ratkaisu on monensuuntainen leikkaus alkuper¨aisess¨a verkossa. N¨ain ollen palautus s¨ailytt¨a¨a approksimointisuhteen.

(b) Muodostetaan approksimointisuhteen s¨ailytt¨av¨a palautus osajoukkotakaisinkytkent¨aon- gelmasta kaarille (A) osajoukkotakaisinkytkent¨aongelmaan solmuille (B). Astetaan kaik- kien alkuper¨aisen verkon kaikkien ei-kiinnostavien solmujen painoksi ∞. Korvataan al- kuper¨aisen verkon jokainen kaari (u, v) kaarilla (u, w_u,v) ja (w_u,v, v), miss¨aw_u,won uusi solmu, johon ei liity muita kaaria. Asetetaan t¨am¨an solmun painoksi uudessa verkossa kaaren (u, v) paino alkuper¨aisess¨a verkossa.

Nyt jokainen ongelman A k¨ayp¨a ratkaisu alkuper¨aisess¨a verkossa voidaan muuttaa ko- konaispainoltaan samaksi ongelman B ratkaisuksi uudessa verkossa. T¨am¨a tapahtuu valitsemalla ongelman B ratkaisuun solmuw_u,v, jos kaari (u, v) kuuluu ongelman A rat- kaisuun. Sama toimii my¨os toiseen suuntaan, jos ongelman B ratkaisu on painoltaan

¨a¨arellinen. N¨ain ollen kysymyksess¨a on approksimointisuhteen s¨ailytt¨av¨a palautus.