582456 Approksimointialgoritmit (kevät 2010) Harjoitus 10 (19. huhtikuuta)
1. (Vazirani 21.3) Olkoon opt(b) pienimmän b-tasapainoisen leikkauksen kapasiteetti ja a puolitus- leikkauksen pseudoapproksimointialgoritmin (luennot s. 322, Vazirani luku 21.6.3) tuottaman(1/3)- tasapainoisen leikkauksen kapasiteetti. Luennolla esitetyn tuloksen mukaana=O(logn)·opt(1/2).
(a) Osoita, että yleisesti opt(1/2) ei ole O(opt(1/3)). Siis ainakaan em. tulos ei vielä riitä osoit- tamaan, että pätisi a = O(logn) · opt(1/3) eli että luentojen algoritmi olisi O(logn)- approksimointialgoritmi pienimmälle(1/3)-tasapainoiselle leikkaukselle.
(b) Muodosta jono vastaesimerkkejä, joka osoittaa, että todella suhde a/opt(1/3) voi kasvaa no- peammin kuinO(logn). Vihje: mieti, mihin luentojen lauseen todistuksessa tarvittiin seikkaa, että 1/3<1/2; tämä liittyy myös seuraavaan tehtävään.
2. (Vazirani 21.4) Olkootb≤1/3jab′> bvakioita. Yleistä puolitusleikkauksen pseudoapproksimointial- goritmi tuottamaanb-tasapainoinen leikkaus, jonka kapasiteetti on korkeintaanO(logn)kertaa pienim- mänb′-tasapainoisen leikkauksen kapasiteetti.
3. (Vazirani 24.13) Metrisessä tuotantolaitosten sijoitteluongelmassa tuotantolaitoksellaion kiinteä avaa- miskustannusfi, joka sallii sen palvella mielivaltaisen monta kaupunkia. Muutetaan ongelmaa niin, että tuotantolaitoksella on kiinteä avaamiskustannussija lisäkustannustijokaista siihen yhdistettyä kaupun- kia kohti. Yhdistämiskustannuksetcijvaikuttavat kuten ennenkin. Osoita, että tämä muunnettu ongelma voidaan palauttaa alkuperäiseen ongelmaan approksimaatiosuhde säilyttäen.
Vihje: melko yksinkertainen muunnos yhdistämiskustannuksiin riittää, mutta muista tarkistaa kolmio- epäyhtälön säilyminen voimassa.
4. (Vazirani 24.8) Otetaan metriseen tuotantolaitosten sijoitteluongelmaan mukaan kapasiteetit. Jokaiselle tuotantolaitoksellei ∈ F on annettu kokonaislukuui, ja laitokseenisaa yhdistää korkeintaan ui kau- punkia. Muotoile ongelman tämä versio lineaarisena kokonaislukuohjelmana. Osoita, että kokonaisluku- raolla ei ole mitään vakioylärajaa.
