582465 Approksimointialgoritmit (kevät 2010) 2. kurssikoe 6.5. kello 9–12 auditorio A111 vastuuhenkilö Jyrki Kivinen
Vastaa kaikkien tehtävien kaikkiin kohtiin. Kokeen maksimipistemäärä on 20 pistettä. Tehtävät eivät välttämät- tä ole vaikeusjärjestyksessä.
1. [8 pistettä] Kurssilla on käsitelty kysyntäpohjaista monihyödykevuota (demands multicommodity flow;
muistin virkistykseksi ongelman määritelmä on toistettu kääntöpuolella).
(a) Esitä ongelma lineaarisena kokonaislukuohjelmana. Muodosta tämän ohjelman lineaarisen löysen- nöksen duaali.
(b) Osoita, että maksimituotantof∗toteuttaa yhtälön
f∗= min
d
P
e∈Ecede
Pk
i=1dem(i)d(si,ti)
.
Tässä minimointi on yli metriikoidend. Siisdliittää kaareenepituudendesiten, että kolmioepäyh- tälö pätee.
2. [6 pistettä] Kurssilla on käsitelty monensuuntaista leikkausongelmaa (multiway cut) sekä osajoukkota- kaisinkytkentäongelmaa kaarille ja solmuille. Muistin virkistykseksi ongelmien määritelmät on toistettu kääntöpuolella. Osoita seuraavat näiden ongelmien väliset suhteet:
(a) Monensuuntaisesta leikkauksesta on approksimointisuhteen säilyttävä palautus osajoukkotakaisin- kytkentäongelmaan kaarille.
(b) Osajoukkotakaisinkytkentäongelmasta kaarille on approksimointisuhteen säilyttävä palautus osa- joukkotakaisinkytkentäongelmaan solmuille.
3. [6 pistettä] Kurssilla on todettu, että PCP-teoreeman perusteella jollainε >0on olemassa raonεtuottava polynomisessa ajassa laskettava palautusfSAT-ongelmasta MAX-3SAT-ongelmaan. Siis kunψ=f(ϕ), missäϕon SAT-tapaukseksi tulkittu propositiologiikan kaava jaψMAX-3SAT-tapaukseksi tulkittu pro- positiologiikan kaava, niin
• josϕ∈SAT, niinOPT(ψ) =m
• josϕ6∈SAT, niinOPT(ψ)<(1−ε)m missämon kaavanψklausuulien lukumäärä.
Osoita kääntäen, että jos on olemassa tällainen palautusf, niinSAT∈PCP(logn,1). (PCP-teoreema seuraa tästä helposti.)
Vihje: Muunna SAT-tapausϕ3SAT-tapaukseksi ψ. Tarkastaja olettaa todistuksen olevan optimaalinen totuusarvoasetus ja saavuttaa virhetodennäköisyyden 1−ε. Toista tarvittavan virhetodennäköisyyden saavuttamiseksi.
Tentissä esiintyvien optimointiongelmien määritelmiä:
Kysyntäpohjaisessa monihyödykevuossa on annettu verkko G = (V, E), päätesolmuparit (s1, t1), . . . ,(sk, tk) ja kaarten kapasiteetit ce. Lisäksi hyödykkeelle i, i = 1, . . . , k, on annettu kysyntädem(i). Oletamme, että kahdella eri hyödykkeelläi6=jpätee{si, ti} 6={sj, tj}.
Tehtävänä on maksimoida tuotanto (throughput)f ehdolla, että hyödykkeenivuo solmustasisolmuun tion ainakinf·dem(i)kaikilla1≤i≤k. Kunkin yksittäisen hyödykkeen vuo toteuttaa normaalit vuon säilymisehdot. Kaareneyli kulkeva vuo saa olla korkeintaance, kun lasketaan yhteen kaikki hyödykkeet ja kumpikin suunta.
Monensuuntaisessa leikkausongelmassa on annettu verkkoG= (V, E), kaarten painofunktiow:E→Q+ ja päätesolmujen joukko{s1, . . . , sk} ⊆ V. Tehtävänä on löytää painoltaan pienin kaarijoukko, jonka poistaminen leikkaa kaikki päätesolmut erilleen eli joka kaikillai 6= j sisältää ainakin yhden kaaren jokaiselta solmujensijasjväliseltä polulta.
Osajoukkotakaisinkytkentäongelmassa kaarille on annettu verkko G = (V, E), joukko kiinnostavia sol- mujaS⊆V ja kaarten painofunktiow: E→Q+. VerkonGsykli on kiinnostava, jos se sisältää ainakin yhden kiinnostavan solmun. Tehtävänä on löytää painoltaan pienin osajoukkotakaisinkytkentäkaarijouk- ko (subset feedback edge set) eli kaarijoukko, joka sisältää ainakin yhden kaaren jokaisesta kiinnostavasta syklistä.
Osajoukkotakaisinkytkentäongelmassa solmuille on annettu verkkoG = (V, E), joukko kiinnostavia sol- mujaS⊆V ja ei-kiinnostavien solmujen painofunktiow:V−S→Q+. VerkonGsykli on kiinnostava, jos se sisältää ainakin yhden kiinnostavan solmun. Tehtävänä on löytää painoltaan pienin osajoukkotakai- sinkytkentäsolmujoukko (subset feedback vertex set) eli ei-kiinnostavien solmujen joukko, joka sisältää ainakin yhden solmun jokaisesta kiinnostavasta syklistä.
2
