Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

Seminar Approximation Algorithms (263-4202-00S) HS09

This seminar will be held in English.

Bernd Gärtner, CAB G32.2, Tel: 01-632 70 26
Matúš Mihaľák, CAB H33.3, Tel: 01-632 04 92
Emo Welzl, CAB G15.2, Tel: 01-632 73 70

Contents

This seminar complements the courses ``Approximate Methods in Geometry'' (last held in FS08) as well as new course ``Approximation Algorothms and Semidefinite Programming'' (held in FS09). Students of the seminar will present original research papers on approximation algorithms, most of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area. This seminar is geared towards topics that are typically covered in a course like ``Approximation Algorithms''.

Dates

First meeting: Friday, September 18, 2009 13:00-15:00, CAB G52.
The plan is to hold the seminar as a block seminar on two to three Fridays during the semester (dates to be agreed upon during first meeting).

Proposed papers

  1. Julián Mestre, Adaptive local ratio, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008 [DOI]
  2. Feng Zou, Xianyue Li, Donghyun Kim, Weili Wu, Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs, Second International Conference on Combinatorial Optimization and Applications, COCOA 2008 [DOI]
  3. Elad Hazan, Sparse Approximate Solutions to Semidefinite Programs, 8th Latin American Theoretical Informatics Conference, LATION 2008, [author website]
  4. Noga Alon, Rina Panigrahy and Sergey Yekhanin, Deterministic Approximation Algorithms for the Nearest Codeword Problem, 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 [ECCC report]
  5. Micah Adler and Brent Heeringa, Approximating Optimal Binary Decision Trees, 11th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 [DOI]
  6. Thanh Nguyen, A simple LP relaxation for the Asymmetric Traveling Salesman Problem, 11th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 [DOI]
  7. Christoph Lenzen, Yvonne Anne Oswald and Roger Wattenhofer, What can be approximated locally? Case study: dominating sets in planar graphs, Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architecture, SPAA 2008 [DOI]
  8. Chandra Chekuri and Iftah Gamzu, Truthful Mechanisms via Greedy Iterative Packing, Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 [DOI]
  9. Francis Chin, HingFung Ting and Yong Zhang, A Constant-competitive Algorithm for Online OVSF Code Assignment, ALGORITHMICA (to appear) [author website]

Conditions

A successful participation in the seminar requires the following:
  1. A rehearsal talk, to be given in front of your supervisor at least one week prior to the plenary talk;
  2. A satisfactory plenary talk;
  3. Attendance at all other talks.
Important: Please also consult and follow our seminar guidelines.