Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Tietoa laitoksesta:

 

Artikkeleita approksimointialgoritmeista

Kurssiin kuuluu lyhyen tiivistelmän kirjoittaminen ja pienen esitelmän pitäminen opiskelijan valitsemasta approksimointialgoritmeihin liittyvästä artikkelista. Tarkemmista yksityiskohdista sovitaan myöhemmin, mutta kirjallisen esityksen pituuden tulisi olla n. 5–10 sivua (Tieteellisen kirjoittamisen kurssin formaatissa) ja suullisen esityksen n. 10–15 minuuttia. Näiden rajoitteiden puitteissa ei kannata yrittääkään esittää yksityiskohtaisia todistuksia, vaan on keskityttävä pääajatusten esittämiseen tiiviisti ja yksinkertaisesti.

Toki opiskelijan itsensä on tarkoitus tutustua asiaan hieman perusteellisemmin, joten sopivan artikkelin etsiminen ja sen lukeminen kannattaa aloittaa hyvissä ajoin. Lähtökohdaksi on alla lueteltu joitain perusartikkeleita, joiden asioita luennoilla ei ehditä käsitellä, sekä joitain melko mielivaltaisesti valittuja esimerkkejä uudemmasta tutkimuksesta. Listaa ei ole tarkoitettu rajoittamaan aihevalintaa, omia aiheita saa mielellään ehdottaa. Sopivia artikkeleita voi löytää esim. alla mainittujen artikkelien tai kurssikirjan viitteistä tai yleisemmin selaamalla konferensseja ja lehtiä, joissa näitä artikkeleita on julkaistu.

Löydettyäsi sopivan artikkelin vahvista aihevalintasi luennoijan kanssa.

Esimerkkiaiheita

Sanjeev Arora. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. Journal of the ACM 45(5):753–782, 1998.

Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis. Linear approximation of shortest superstrings. Journal of the ACM 41(4):630–647, 1994.

G. Borradaile, P. N. Klein and C. Mathieu. A polynomial-time approximation scheme for Euclidean Steiner forest. Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pages 115–124, 2008.

Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber. On the sum-of-squares algorithm for bin packing. Journal of the ACM 53(1):1–65, 2006

Bruno Escoffiera and Vangelis Th. Paschos. Completeness in approximation classes beyond APX. Theoretical Computer Science 359(1–3):369–377, 2006.

Gregory Gutin and Anders Yeo. Introduction to domination analysis. Technical Report CSD-TR-04-01, Royal Holloway, University of London, 2004.

Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi and Vijay V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Journal of the ACM 50(6):795–824, 2003.

Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM Journal of Computing 18(6):1149–1178, 1989.

Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman and Ravi Sundaram. Universal approximations for TSP, Steiner tree, and set cover. Proc. 37th Annual ACM Symposium on Theory of Computing, pages 386–395, 2005.

H. N. Nguyen and K. Onak. Constant-time approximation algorithms via local improvements. Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pages 327–336, 2008.

Tobias Polzin and Siavash Vahdati Daneshmand. Improved algorithms for the Steiner problem in networks. Discrete Applied Mathematics 112(1–3):263–300, 2001.

Mohit Singh and Lap Chi Lau. Approximating minimum bounded degree spanning trees to within one of optimal. Proc. 39th Annual ACM Symposium on Theory of Computing, pages 661–670, 2007.


17. huhtikuuta 2010 Jyrki Kivinen