Approksimointialgoritmit (kev¨at 2010) Harjoitus 10 (19. huhtikuuta) Ratkaisuja (Jouni Siren)

Approksimointialgoritmit (kev¨ at 2010) Harjoitus 10 (19. huhtikuuta)

Ratkaisuja (Jouni Siren)

1. Osoitetaan, ett¨a pienimm¨an puolitusleikkauksen pseudoapproksimointialgoritmin tuottama ratkaisu ei ole v¨altt¨am¨att¨a hyv¨a ratkaisu (1/3)-tasapainoiseen leikkaukseen.

(a) Muodostetaan n solmun verkko ja sen leikkaus (S, S) siten, ett¨a |S| = n/3. Verk- koon kuuluvat ne kaaret, joiden p¨a¨at ovat leikkauksessa (S, S) samalla puolella. Nyt OPT1/3 = 0 jaOPT1/2=n²/12, joten puolitusleikkauksen ja (1/3)-tasapainoisen leik- kauksen optimiratkaisut voivat poiketa toisistaan huomattavasti.

(b) Tarkastellaannsolmun verkkoa, jonka solmut jakautuvat joukkoihinA,B jaC. Olete- taan, ett¨a |A|=n/3−1, |B|=n^1/2 ja|C|= 2n/3 + 1−n^1/2. JoukonA solmuihin ei liity kaaria. JoukotB jaCovat klikkej¨a, mink¨a lis¨aksi jokaisesta joukonB solmusta on kaarin^1/4joukonCsolmuun.

Optimaalisessa (1/3)-tasapainoisessa leikkauksessa pienemm¨alle puolelle kuuluvat jou- kon A solmut sek¨a jokin joukon B solmuista. N¨ain ollen OPT_1/3 = n^1/2 +n^1/4 −1.

Algoritmi puolestaan valitsee ensin kaikki joukonAsolmut, koska niihin ei liity kaaria.

Koska leikkaus ei ole viel¨a riitt¨av¨an tasapainoinen, joutuu algoritmi t¨aydent¨am¨a¨an sit¨a joukkojen B ja C solmuilla. Seuraavaksi algoritmi etsii osajoukon W ⊂ B∪C, mis- s¨a |W| ≤ |B∪C|/2 ja osajoukon W kaarilaajentuma on korkeintaan O(logn) kertaa optimaalista suurempi joukossaB∪C.

Optimaalinen valinta olisi joukko B, jonka kaarilaajentuma on n^1/4. Yhdenkin joukon C solmun valitseminen tuottaisi kaarilaajentuman Ω(n^1/2), joten t¨aytyy olla W ⊆B.

Jos taas |W| ≤ |B|/2, tulee kaarilaajentumaksi silloinkin Ω(n^1/2). Valitun osajoukon W ⊆Bkoko on siis Θ(n^1/2), joten algoritmin l¨oyt¨am¨an leikkauksen (A∪W, C∪B\W) kooksi tulee Ω(n^3/4).

2. Olkoot b ja b⁰ vakioita, b ≤1/3 ja b < b⁰ ≤ 1/2. Luennoilla (sivu 322) esitettiin algoritmi l¨oyt¨a¨a (1/3)-tasapainoisen leikkauksen, jonka koko on korkeintaan O(logn)·OPT_1/2. Algo- ritmi yleistyy suoraviivaisesti niin, ett¨a se l¨oyt¨a¨ab-tasapainoisen leikkauksen, jonka koko on korkeintaanO(logn)·OPT_b⁰.

Kohdan 2 pys¨ahtymisehdoksi tulee |U| ≥ bn. Todistuksessa (sivut 323–324) tulee l¨ahinn¨a kiinnitt¨a¨a huomiota siihen, ett¨a suorituksen aikana|V⁰| ≥(1−b)n. Jos siis (T, T) on pienin b⁰-tasapainoinen leikkaus, joukkoihinV⁰∩T jaV⁰∩T kuuluu kumpaankin ainakin (b⁰−b)n solmua. Todistus etenee t¨alt¨a pohjalta kuten luennoilla.

3. Tarkastellaan metrisen tuotantolaitosten sijoitteluongelman muunnelmaa, jossa jokaisella lai- toksellai∈F on avaamiskustannuksensilis¨aksi lis¨akustannusti jokaista siihen liitetty¨a kau- punkia kohti. Muunnelma palautuu luonnollisella tavalla ongelman tavanomaiseen versioon:

lis¨at¨a¨an jokaiseen yhdist¨amiskustannukseencij vastaava lis¨akustannus ti kaikilla laitoksilla i∈F ja kaupungeillaj ∈C.

Osoitetaan, ett¨a kolmioep¨ayht¨al¨o pysyy edelleen voimassa. Olkooti, i⁰∈F tuotantolaitoksia jaj, j⁰ ∈C kaupunkeja. Koska ongelmaa vastaava verkko on kaksijakoinen, riitt¨a¨a osoittaa, ettei polkup=j→i⁰→j⁰ →imuutu lyhyemm¨aksi kuin suora reittij →i. Alkuper¨aisest¨a verkosta tiedet¨a¨an kolmioyht¨al¨on nojalla cost(p) = c_i⁰_j +c_i⁰_j⁰ +c_ij⁰ ≥ c_ij. Muunnetussa verkossa taas p¨atee

cost⁰(p) = (ci⁰j+ti⁰) + (ci⁰j⁰+ti⁰) + (cij⁰+ti) =cost(p) + 2ti⁰+ti≥cij+ti, joten kolmioep¨ayht¨al¨o on edelleen voimassa.

4. Lis¨at¨a¨an metriseen tuotantolaitosten sijoitteluongelmaan kapasiteettiui jokaiselle tuotanto- laitoksellei∈F. Rajoite tarkoittaa, ett¨a laitokseeni saa kytke¨a korkeintaanui kaupunkia.

Lineaariseksi ohjelmaksi tulee nyt

minimoi X

i∈F,j∈C

c_ijx_ij+X

i∈F

f_iy_i ehdoilla X

i∈F

x_ij ≥1 kaikillaj∈C u_iy_i−X

j∈C

x_ij≥0 kaikillai∈F

x_ij ∈ {0,1} kaikillai∈F jaj∈C yi∈ {0,1} kaikillai∈F

Tarkastellaan kahta laitosta ja n kaupunkia. Laitos 1 on halpa, ja sill¨a p¨atee u₁ = n−1, f₁= 1 jac_1j = 1 kaikillaj∈C. Laitos 2 on puolestaan kallis, ja sill¨a p¨ateeu₂=n,f₂=n² jac_2j = 1 kaikilla j ∈ C. Optimaalisessa murtolukuratkaisussa n−1 kaupunkia kytket¨a¨an halpaan laitokseen ja viimeinen kaupunki kalliiseen laitokseen, jolle asetetaan y2 = 1/n.

Optimaalisessa kokonaislukuratkaisussa taas kallis laitos on pakko ottaa k¨aytt¨o¨on kokonaan, jolloin kaikki kaupungit voidaan kytke¨a siihen. Niinp¨aOPTf = 2n+ 1 ja OPT=n²+n.