Approksimointialgoritmit (kev¨at 2010) Harjoitus 4 (15. helmikuuta) Ratkaisuja (Jouni Siren)

Approksimointialgoritmit (kev¨ at 2010) Harjoitus 4 (15. helmikuuta)

Ratkaisuja (Jouni Siren)

1. Tarkastellaan ahneita algoritmeja repunpakkausohjelmaan. Olkoot esineeta1, . . . , an yksik- k¨otuotonprofit(a)/size(a) mukaisessa laskevassa j¨arjestyksess¨a ja repun kokoB.

(a) Algoritmi, joka valitsee esineeta1, . . . , a_k−1, voi tuottaa mielivaltaisen huonon approk- simointisuhteen. Vihje esimerkin l¨oyt¨amiseen saadaan seuraavasta kohdasta: joskus esi- neenak valitseminen olisi parempi vaihtoehto.

Olkoon B = 2 ja 0 < α(n) < 1 jokin polynomisessa ajassa laskettava funktio. Ahne algoritmi valitsee ensimm¨aiset k−1 esinett¨a, joille oletetaan size(ai) = profit(ai) = α(n)/(k−1) kaikilla i < k. N¨aiden esineiden yksikk¨otuotto on profit(a_i)/size(a_i) = 1.

Ahneen algoritmin valitsemien esineiden yhteiskooksi ja kokonaistuotoksi tuleeα(n).

Asetetaan size(a_k) = 2 ja profit(a_k) = 1. Nyt yksikk¨otuotoksi tulee aikaisempia esi- neit¨a pienempi profit(a_k)/size(a_k) = 1/2, eik¨a esine a_k mahdu en¨a¨a mukaan ahneen algoritmin valitsemien esineiden joukkoon. Kuitenkin valitsemalla pelk¨ast¨a¨an esine a_k saadaan kokonaistuotoksi profit(ak) = 1, joten ahneen algoritmin approksimointisuhde ei voi olla parempi kuinα(n). Koskaα(n) voi olla mielivaltaisen l¨ahell¨a nollaa, voi my¨os approksimointisuhteesta tulla mielivaltaisen huono.

(b) Merkit¨a¨an R1 = {a1, . . . , a_k−1} ja R2 ={ak}. Koska edellisen kohdan ahne algoritmi valitsee joukonR1mutta ei en¨a¨a alkiotaak, t¨aytyy ollasize(R1)+size(R2)> B. Toisaal- ta ainakin toisella n¨aist¨a joukoista t¨aytyy p¨ate¨aprofit(Ri)≥(profit(R1) +profit(R2))/2.

Lis¨aksi profit(R1) +profit(R2)≥OPT, sill¨a n¨aiden joukkojen esineet ovat yksikk¨otuo- toltaan suurimpia ja niiden yhteiskoko on repun kokoa suurempi. Valitsemalla parempi n¨aist¨a joukoista saadaan siis kokonaistuotoksi max(profit(R1),profit(R2))≥OPT/2.

2. Teht¨av¨an yksityiskohtainen ratkaisu l¨oytyy l¨ahteeksi annetun artikkelin luvusta 3. T¨ass¨a l¨ahinn¨a hahmotellaan ratkaisua.

Annettuna onnpositiivista kokonaislukuaa₁< . . . < a_n. K¨aypi¨a vastauksia ovat osajoukko- paritS₁, S₂⊆ {1, . . . , n}, joilla A₁=P

i∈S1a_i≥P

i∈S2a_i=A₂. Tavoitteena on minimoida suhdeA1/A2ja p¨a¨ast¨a kertoimen 1 +εsis¨a¨an optimaalisesta ratkaisusta.

Algoritmi

Hahmotellaan ensin pseudopolynominen algoritmi ongelmaan. Algoritmi t¨aytt¨a¨a taulukon t[0. . . n,0. . .Pn

i=1a_i] niin, ett¨a t[i, j] = 1, jos esineist¨a a₁, . . . , a_i voidaan valita osa niin, ett¨a alkio a_i on mukana ja yhteispainoksi tulee j. Jos jollain j p¨atee t[i₁, j] = t[i₂, j] = 1 joillaini₁6=i₂, ovat n¨am¨a osajoukot erillisi¨a pienimm¨all¨a t¨allaisellaj. T¨allaisessa tapauksessa sanotaan, ett¨a optimiratkaisu on eksakti. Muussa tapauksessa jokaisella j p¨ateet[i, j] = 1 korkeintaan yhdell¨ai, ja optimiratkaisu l¨oytyy k¨aym¨all¨a l¨api kaikki osajoukkoparit.

FPTAS muodostaa ja ratkaisee instanssit Im kaikilla m = 2, . . . , n ja palauttaa parhaan l¨oyt¨am¨ans¨a ratkaisun. Kukin instanssi Im koostuu m pienimm¨ast¨a alkiosta a1, . . . , am, ja siin¨a k¨aytet¨a¨an skaalauskerrointak(m) =ε²·am/(2m).

Olkoon n0 ≤ n suurin arvo, jolla k(n0) < 1. Jos m ≤ n0, ovat instanssin Im luvut po- lynomisen kokoisia ja se voidaan ratkaista optimaalisesti pseudopolynomisella algoritmilla.

Muussa tapauksessa muodostetaan muunnettu instanssiI_m⁰ niist¨a arvoista a⁰_i =bai/k(m)c, joillaa⁰_i ≥m/ε. Olkoont≥1 t¨allaisten arvojen m¨a¨ar¨a.

Jos t = 1, olkoon j pienin ei-negatiivinen kokonaisluku, jolla Pm−1

i=j+1a_i < a_m. Jos j = 0, valitaanS₁={m} jaS₂ ={1, . . . , m−1}, muussa tapauksessa taasS₁={j, . . . , m−1} ja S2 = {m}. J¨alkimm¨aisess¨a tapauksessa siis vasta alkion aj lis¨a¨aminen kasvatti osajoukkoa S1vastaavan summan suuremmaksi kuin osajoukkoa S2 vastaava summa.

Jost >1, ratkaistaanI_m⁰ pseudopolynomisella algoritmilla. Jos l¨oytynyt ratkaisu on eksakti, palautetaan se. Muussa tapauksessa k¨ayd¨a¨an l¨api kaikki luvuistam−t+ 1, . . . , msaatavien erillisten osajoukkojen muodostamat parit (R1, R2), joissa toinen joukoista sis¨alt¨a¨a luvunm, ja palautetaan paras seuraavalla mekanismilla saatavista osajoukkopareista (S1, S2).

Oletetaan, ett¨a B₁=P

i∈R1a_i≥P

i∈R2a_i=B₂. Olkoon j pienin ei-negatiivinen kokonais- luku, jollaB2+Pm−t

i=j+1ai< B1. Josj= 0, palautetaanS1=R1jaS2=R2∪ {1, . . . , m−t}.

Muuten josm∈R1, palautetaan S1=R2∪ {j, . . . , m−t} jaS2=R1. Muuten palautetaan S1=R1jaS2=R2∪ {j+ 1, . . . , m−t}.

Todistus

Osoitetaan algoritmin toimivan polynomisessa ajassa arvojennja 1/εsuhteen ja saavuttavan approksimointisuhteen 1 +ε.

Algoritmin useimmat osat toimivat selv¨asti polynomisessa ajassa. Ainoa ep¨aselv¨a kohta on osajoukkoparien (R1, R2) l¨apik¨aynti. Koska tapauksenI_m⁰ optimiratkaisu ei ole eksakti, ovat kaikki 2^t eri osajoukkoja vastaavien alkioiden summaa erisuuria. Koskaa⁰_m ≤2m/ε², t¨ay- tyy olla 2^t ≤Pm

i=m−t+1a⁰_i ≤2m²/ε², koska osajoukkoja vastaavien alkioiden summat ovat kokonaislukuja. Luvunt t¨aytyy siis t¨ass¨a tapauksessa olla logaritmisen suuruinen, joten os- ajoukkoparit voidaan k¨ayd¨a l¨api polynomisessa ajassa.

Olkoon m jatkossa suurin indeksi, jolla am on mukana optimiratkaisussa. Osoitetaan, ett¨a algoritmi l¨oyt¨a¨a instanssiin Im ratkaisun, jolla A1/A2 ≤ (1 +ε)·OPT. Riitt¨a¨a tarkastella tapauksia, joissam > n0.

Jost= 1 jaj= 0, l¨oydetty ratkaisu on optimaalinen, koskaam kuuluu optimiratkaisuun ja on painavampi kuin muut alkiot yhteens¨a. Tapauksessat= 1 jaj >0 taasa⁰_j< m/εja siksi

aj <(a⁰_j+ 1)·k(m)< 2m

ε · ε²·am

2m =εam eli P

i∈S1ai

P

i∈S2a_i ≤1 + aj

a_m <1 +ε.

Jos tapauksessat >1 muunnetun instanssinI_m⁰ ratkaisu on eksakti, p¨atee P

i∈S1ai

P

i∈S2ai

≤ P

i∈S1k(m)·(1 +a⁰_i) P

i∈S2k(m)·a⁰_i = P

i∈S1a⁰_i P

i∈S2a⁰_i + |S₁| P

i∈S2a⁰_i ≤1 + t

m/ε<1 +ε.

J¨aljell¨a on tapaus t > 1, jossa muunnetun instanssin ratkaisu ei ole eksakti. Jos parhaalla parilla (R1, R2) p¨ateej = 0, on sit¨a vastaava ratkaisu (S1, S2) optimaalinen parin (R1, R2) kanssa yhteensopivien ratkaisujen joukossa. Jos kaikilla pareilla p¨ateej= 0, l¨oytyy n¨ain my¨os optimiratkaisu.

Muuten toista osajoukoistaS1 ja S2 vastaavien alkioiden yhteispaino on B1 ja toisen taas v¨alill¨a [B1−aj, B1+aj]. Lis¨aksi tiedet¨a¨an, ett¨am∈S2. N¨ain ollen p¨atee

P

i∈S1a_i P

i∈S₂a_i ≤1 + aj

P

i∈S₂a_i ≤1 + aj

a_m <1 +ε sill¨a tapauksent= 1 mukaisestiaj/am< ε.2

3. Tarkastellaan rajoitettua versiota First-Fit-algoritmista laatikonpakkausongelmaan. Algorit- mi k¨ay esineeta₁, . . . , a_nl¨api mielivaltaisessa j¨arjestyksess¨a ja yritt¨a¨a sijoittaa kunkin esineen sill¨a hetkell¨a pakattavana olevaan laatikkoon. Jos esine ei mahdu, algoritmi julistaa laatikon t¨aydeksi ja siirtyy pakkaamaan seuraavaa laatikkoa. Osoitetaan, ett¨a t¨am¨akin versio algorit- mista saavuttaa approksimointisuhteen 2.

Optimiratkaisulle p¨ateeOPT≥Pn

i=1ai. Oletetaan, ett¨a rajoitettu First-Fit k¨aytt¨a¨a yhteens¨a m laatikkoa, ja k¨ayd¨a¨an sen pakkaamat laatikot l¨api j¨arjestyksess¨a. Pidet¨a¨an l¨apik¨aynnin yhteydess¨a yll¨a invarianttia, ett¨akensimm¨aist¨a laatikkoa on pakattu keskim¨a¨arin v¨ahint¨a¨an puolilleen.

Arvolla k = 0 invariantti on triviaalisti tosi. Jos laatikko k+ 1 on v¨ahint¨a¨an puolillaan, invariantti on tosi my¨os arvollak+ 1. Jos taas laatikkok+ 1< mon alle puolillaan, t¨aytyy t¨am¨an johtua siit¨a ettei seuraava esine en¨a¨a mahtunut laatikkoon. N¨ain ollen laatikoissa k+ 1 ja k+ 2 t¨aytyy olla yhteens¨a enemm¨an esineit¨a kuin yhteen laatikkoon mahtuu, joten invariantti on tosi my¨os arvolla k+ 2. Induktiolla saadaan, ett¨a ensimm¨aiset m−1 tai m laatikkoa ovat keskim¨a¨arin v¨ahint¨a¨an puolillaan riippuen siit¨a, onko laatikkompakattu alle vai v¨ahint¨a¨an puolilleen.

Jos my¨os viimeinen laatikko on v¨ahint¨a¨an puolillaan, p¨ateem≤2·Pn

i=1a_i ≤2·OPT. Jos taas viimeinen laatikko on alle puolillaan, p¨ateem−1<2·Pn

i=1a_i ≤2·OPT. Koskamja OPTovat kokonaislukuja, seuraa my¨os t¨ast¨am≤2·OPT. Rajoitettu First-Fit saavuttaa siis molemmissa tapauksissa approksimointisuhteen 2.

Olkoon k > 0 jokin kokonaisluku. Tiukka esimerkki koostuu 2k suuresta esineest¨a, joiden koko on 0,5, ja 2kpienest¨a esineest¨a, joiden koko on _2k¹. Optimaalisessa pakkauksessa suuret esineet pakataanklaatikkoon ja pienet esineet yhteen laatikkoon, mist¨a seuraaOPT=k+ 1.

Jos suuria ja pieni¨a esineit¨a kuitenkin tulee vuorotellen, pakkaa rajoitettu First-Fit jokaiseen laatikkoon yhden suuren ja yhden pienen esineen. N¨ain laatikoita tarvitaan yhteens¨a 2k kappaletta.

4. Olkoon joukkopeiteongelman perusjoukkoU, osajoukkojen kokoelmaS ja kustannusfunktio c. Ongelmaa vastaava l¨oysennetty lineaarinen ohjelma duaaleineen on seuraava:

minimoi X

S∈S

c(S)xS (primaali)

ehdolla X

S:e∈S

x_S ≥1 kaikilla e∈U xS ≥0 kaikilla S∈ S maksimoi X

e∈U

ye (duaali)

ehdolla X

e:e∈S

ye≤c(S) kaikilla S∈ S ye≥0 kaikilla e∈U Olkootxjay primaalin ja duaalin k¨aypi¨a ratkaisuja, joilla p¨atee

(a) kaikillae∈U: josye6= 0, niinP

S:e∈SxS= 1;

(b) kaikillaS∈ S: josxS 6= 0, niinP

e:e∈Sye=c(S).

T¨all¨oin n¨aille ratkaisuille p¨atee X

S∈S

c(S)xS =X

S∈S

X

e:e∈S

ye

!

xS =X

e∈U

X

S:e∈S

xS

!

ye=X

e∈U

ye.

Primaalin ja duaalin kohdefunktiot saavat siis samat arvot, kun ehdot (a) ja (b) ovat voi- massa.