Approksimointialgoritmit (kev¨at 2010) Harjoitus 11 (26. huhtikuuta) Ratkaisuja (Jouni Siren)

Approksimointialgoritmit (kev¨ at 2010) Harjoitus 11 (26. huhtikuuta)

Ratkaisuja (Jouni Siren)

1. Laitostensijoitteluongelman approksimointialgoritmin vaiheessa 2 valitaan v¨aliaikaisesti avat- tujen laitosten muodostamasta verkostaH maksimaalinen riippumaton joukko I, jonka lai- tokset avataan. VerkossaH on kaari laitostenijai⁰ v¨alill¨a, jos jokin kaupunkijon maksanut laitostenijai⁰ avaamisesta eli kaaret (i, j) ja (i⁰, j) ovat erityisi¨a alkuper¨aisess¨a verkossa.

Muutetaan algoritmia niin, ett¨a laitosten i ja i⁰ v¨alille tulee kaari, jos jokin kaupunki j on maksanut niin paljon, ett¨a se voitaisiin yhdist¨a¨a kumpaan tahansa laitoksistaijai⁰. T¨all¨oin sanotaan, ett¨a alkuper¨aisen verkon kaaret (i, j) ja (i⁰, j) ovat tiukkoja. Osoitetaan, ett¨a nyt luentojen lemma 3.76 ei en¨a¨a p¨ade, vaan laitokseen i yhdistetyll¨a kaupungilla j voi olla c_ij >3α^e_j, miss¨aα^e_j on yhdist¨amiseen k¨aytetty osuus kaupungin j maksamasta hinnasta.

Tarkastellaan verkkoa, jossa on laitoksetijai⁰sek¨a kaupungitj,j⁰jak. Kummankin laitoksen avauskustannus onf₁=f₂= 1, ja yhdist¨amiskustannuksille p¨ateec_i⁰_j = 1,c_ij⁰ =c_i⁰_j⁰ = 100 jac_ik = 100. Muut yhdist¨amiskustannukset saadaan lyhimmist¨a poluista. Algoritmi etenee nyt seuraavasti:

t αj αj⁰ αk βi βi⁰ Tapahtumat

0 0 0 0 0 0

1 1 1 1 0 0 (i⁰, j) tiukka 2 2 2 2 0 1 (i⁰, j) erityinen

100 2 100 100 0 1 (i, j⁰),(i⁰, j⁰) ja (i, k) tiukkoja 101 2 100 101 1 1 (i, k) erityinen

Lihavoitu arvo tarkoittaa, ett¨a kyseinen kaupunki on yhdistetty tai laitos on v¨aliaikaisesti avattu.

Vaiheessa 1 avattiin siis molemmat laitokset v¨aliaikaisesti. Verkkoon H tulee niiden v¨alille kaari, sill¨a kaaret (i, j⁰) ja (i⁰, j⁰) ovat tiukkoja. Jos riippumattomaksi joukoksi valitaan{i}, yhdistet¨a¨an kaikki kaupungit laitokseeni. Koskac_ij= 201, p¨atee sillec_ij >3α^e_j = 6.

Ongelma voidaan korjata numeroimalla laitokset sen mukaan, miss¨a j¨arjestyksess¨a ne avattiin, ja valitsemalla verkon H maksimaaliseksi riippumattomaksi joukoksi niist¨a leksikografisesti ensimm¨ainen. Lis¨aksi jos kaupunkijjoudutaan yhdist¨am¨a¨an ep¨asuorasti johonkin sen yhdis- tystodisteeni⁰ riippumattomassa joukossa I olevaan naapuriin verkossaH, valitaan n¨aist¨a naapureista j¨arjestyksess¨a ensimm¨ainen. Olkoon t¨am¨a laitosi. Koska H on leksikografisesti ensimm¨ainen maksimaalinen riippumaton joukko, seuraa t¨ast¨a i < i⁰.

On syyt¨a huomata, ett¨a vaikka monta asiaa saattaa tapahtua hetkell¨a t, on n¨aill¨a tapahtu- milla aina jokin j¨arjestys. Jos siis jollain kaupungillajmuuttuisi samanaikaisesti monta kaar- ta tiukoiksi, ei n¨ait¨a muuttumisia kuitenkaan en¨a¨a k¨asitell¨a sen j¨alkeen, kun jokin tiukaksi muuttunut kaari (i, j) yhdist¨a¨a kaupungin v¨aliaikaisesti avoimeen laitokseeni.

Tarkastellaan kaupunkiaj, joka on yhdistetty ep¨asuorasti laitokseenija jonka yhdistystodiste on laitos i⁰. Laitosten i ja i⁰ v¨alill¨a on kaari verkossa H, joten kaaret (i, j⁰) ja (i⁰, j⁰) ovat tiukkoja jollain kaupungillaj⁰. Koska laitosi⁰ on kaupunginj yhdistystodiste, p¨atee selv¨asti α_j ≥c_i⁰_j.

Oletetaan, ett¨a hetkell¨atlaitosion avautunut v¨aliaikaisesti ja kaupunkij⁰on liittynyt siihen.

Koska my¨os kaari (i⁰, j⁰) on tiukka, t¨aytyy sen olla muuttunut tiukaksi ennen hetke¨a t, eli ci⁰j⁰ ≤ t. Jos kaari (i, j⁰) muuttui tiukaksi hetkell¨a t, ei laitos i⁰ voinut olla viel¨a auki. Jos taas laitosiavautui hetkell¨at, ei laitosi⁰voinut viel¨a auki, koskai < i⁰. Laitosi⁰ avautuu siis vasta hetkent j¨alkeen. Koska αj kasvaa, kunnes laitosi⁰ avautuu, t¨aytyy ollaαj≥t≥ci⁰j⁰. Toisaalta αj⁰ lakkaa kasvamasta viimeist¨a¨an hetkell¨a t, mist¨a seuraa αj ≥ t ≥ αj⁰ ≥ cij⁰. N¨ain ollen lemma 3.76 on taas voimassa.

2. Esitet¨a¨an tuotantolaitosten sijoitteluongelmaa vastaava kokonaislukuohjelma. Oletetaan, ett¨a jokaisella tuotantolaitoksellai∈F on kapasiteettiu_ija ett¨a kukin laitos voidaan avata useita kertoja.

minimoi X

i∈F,j∈C

c_ijx_ij+X

i∈F

f_iy_i ehdoilla X

i∈F

xij ≥1 kaikillaj∈C

y_i−x_ij≥0 kaikillai∈F jaj∈C u_iy_i−X

j∈C

x_ij≥0 kaikillai∈F

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

y_i∈N kaikillai∈F

Lineaarisessa l¨oysenn¨oksess¨a on luonnollisestixij ≥0 jayi≥0. Duaaliksi tulee t¨all¨oin:

maksimoi X

j∈C

αj

ehdoilla αj−βij−γi≤cij kaikillai∈F jaj∈C uiγi+X

j∈C

βij≤fi kaikillai∈F αj≥0 kaikillaj∈C

βij ≥0 kaikillai∈F jaj∈C γi≥0 kaikillai∈F

Kiinnitet¨a¨an duaalissa γ_i = 3f_i/4u_i jolloin sit¨a vastaava primaali kuvaa tuotantolaitosten sijoitteluongelmaa ilman kapasiteetteja:

minimoi X

i∈F,j∈C

c_ij+3fi

4u_i

x_ij+X

i∈F

fi

4Y_i ehdoilla X

i∈F

x_ij ≥1 kaikillaj∈C

Yi−xij ≥0 kaikillai∈F jaj∈C

xij ≥0 kaikillai∈F jaj∈C

Yi≥0 kaikillai∈F

Kolmioyht¨al¨o on edelleen voimassa, joten ongelma voidaan ratkaista luennoilla (sivut 330–

349) esitetyll¨a 3-approksimointialgoritmilla. N¨ain saadaan kokonaislukuratkaisu (x, Y), jonka kustannukselle p¨atee

X

i∈F,j∈C

cij+ 3fi

4ui

xij+ 3X

i∈F

fi

4Yi ≤3X

j∈C

αj. (1)

T¨ast¨a saadaan k¨ayp¨a ratkaisu alkuper¨aiseen ongelmaan avaamalla kukin laitos riitt¨av¨a m¨a¨ar¨a kertoja:

yi=

Pj∈Cx_ij ui

kaikilla i∈F.

KoskaYi= 1, jos laitokseenFi on kytketty kaupunkeja, p¨atee nyt y_i≤Y_i+

P

j∈Cxij

u_i kaikilla i∈F. (2)

Ep¨ayht¨al¨oist¨a 1 ja 2 seuraa nyt X

i∈F,j∈C

c_ijx_ij+3 4

X

i∈F

f_iy_i≤3X

j∈C

α_j.

Nyt siis (x, y) on k¨ayp¨a ratkaisu alkuper¨aiseen kokonaislukuohjelmaan, ja sill¨a p¨atee X

i∈F,j∈C

cijxij+X

i∈F

fiyi≤4X

j∈C

αj,

joten meill¨a on 4-approksimointialgoritmi tarkasteltavaan ongelmaan.

3. Esitet¨a¨an vakioapproksimointialgoritmi ryv¨astysongelmaan.

Oletetaan, ett¨a ett¨a optimaalisessa ryv¨astyksess¨a jotkin pisteet u₁, . . . , u_t on liitetty keski- pisteeseenc = (u₁+· · ·+u_t)/t, ja u₁ on n¨aist¨a pisteist¨a l¨ahimp¨an¨a keskusta c. Jos ryv¨as- tyskeskuksena k¨aytett¨aisiinkin pistett¨au1, saataisiin n¨aiden pisteiden osuudeksi ryv¨astyksen kustannuksesta

t

X

i=1

||ui−u1||²₂=

t

X

i=1

||ui−c||²₂+t||u1−c||²₂≤2

t

X

i=1

||ui−c||²₂.

T¨ass¨a yht¨al¨o seuraa siit¨a, ett¨acon pisteidenui keskiarvo, ja ep¨ayht¨al¨o taas siit¨a, ett¨au1on pisteist¨a l¨ahinn¨a keskustac.

Valitsemalla pisteetv1, . . . , vn sek¨a kaupunkien ett¨a laitosten joukoksi saadaan siisk-medi- aaniongelman tapaus, jonka optimiratkaisu on korkeintaan kaksi kertaa kalliimpi kuin ryv¨as- tysongelman tapauksen. Lis¨aksi jokainenk-mediaaniongelman ratkaisu on my¨os sellaisenaan ryv¨astysongelman ratkaisu.

Ylim¨a¨ar¨aisen¨a haasteena on kuitenkin se, ett¨a pisteiden v¨aliset et¨aisyydet eiv¨at toteuta kol- mioep¨ayht¨al¨o¨a, vaan ainoastaan et¨aisyyksien neli¨ojuuret. T¨am¨a vaikuttaa k-mediaaniongel- man approksimointialgoritmissa aliohjelmana k¨aytett¨av¨a¨an tuotantolaitosten sijoitteluongel- man approksimointialgoritmiin niin, ett¨a approksimointikerroin 3 muuttuukin kertoimeksi 9. Ero tulee lemmasta 3.76, jonka todistuksessa tarvitaan kolmioep¨ayht¨al¨o¨a. Jos yhdist¨a- miskustannuksen neli¨ojuuri enint¨a¨an kolminkertaistuu ep¨asuorassa yhdist¨amisess¨a, kasvaa kustannus korkeintaan yhdeks¨ankertaiseksi.

Kolmioep¨ayht¨al¨o¨a tarvitaan my¨os py¨orist¨amisen yhteydess¨a lemmassa 3.79. Luentojen sivun 369 toinen ep¨ayht¨al¨orivi muuttuu nyt muotoon

√ci₃,j ≤2√

ci₁,j+√

ci₂,j ⇐⇒ ci₃,j ≤4ci₁,j + 4√

ci₁,jci₂,j+ci₂,j

ja sit¨a seuraava odotusarvo vastaavasti muotoon

E[cφ(j),j] ≤ bci₂,j+a²ci₁,j+ab(4ci₁,j+ 4√

ci₁,jci₂,j+ci₂,j)

= aci₁,j(a+ 4b) +bci₂,j(1 +a) + 4ab√

ci₁,jci₂,j

≤ aci₁,j(1 + 3b) +bci₂,j(1 +a) + 4ab·ci₁,j+ci₂,j

2

= ac_i1,j(1 + 5b) +bc_i2,j(1 + 3a)

≤ (aci₁,j+bci₂,j)(1 + 5·max{a, b}).

Py¨orist¨amisvaihe kasvattaa siis kustannuksen korkeintaan kuusinkertaiseksi (k-mediaanion- gelmassa kaksinkertaiseksi). L¨oydetty ratkaisu on siis korkeintaan 2·9·6 = 108 kertaa huo- nompi kuin ryv¨astysongelman optimiratkaisu.

4. Osoitetaan, ett¨aPCP(logn, poly(n))⊆NP.

Tarkastellaan mielivaltaista luokanNPkielt¨aLja muodostetaan sille ratkaisualgoritmiA, jo- ka simuloi tarkastajaa. AlgoritmiA aloittaa arvaamalla ep¨adeterministisesti sy¨otett¨a xvas- taavan todistukseny. T¨am¨an j¨alkeen se k¨ay l¨api kaikki mahdolliset tarkastajan satunnaisjo- not ja selvitt¨a¨a jokaisella satunnaisjonollar, hyv¨aksyyk¨o tarkastaja sy¨otteenxtodistuksella yja satunnaisjonolla r.

Koska erilaisia satunnaisjonoja on polynominen m¨a¨ar¨a, toimii algoritmi A polynomisessa ajassa. Jos sy¨otexkuuluu kieleenL, tarkastaja hyv¨aksyy sy¨otteen kaikilla satunnaisjonoilla.

Muussa tapauksessa tarkastaja hylk¨a¨a sy¨otteen ainakin puolella satunnaisjonoista. Polynomi- sessa ajassa toimiva ep¨adeterministinen algoritmiAtunnistaa siis kielenL, joten kieli kuuluu luokkaanNP.

Edell¨a todistettiin PCP(logn, poly(n)) ⊆ NP. PCP-teoreeman perusteella tiedet¨a¨an, ett¨a PCP(logn,1) =NP. Koska jokainen luokanPCP(logn,1) mukainen tarkastaja on my¨os luokan PCP(logn, poly(n)) mukainen tarkastaja, p¨ateePCP(logn,1)⊆PCP(logn, poly(n)). N¨ain ol- len p¨ateePCP(logn,1) =PCP(logn, poly(n)).