Geometric Optimization (202-2-5311)
Prof. Matya Katz
Tue 14-16, Thu 10-12
The course covers various topics in geometric optimization.
Prerequisite: Design of Algorithms 202-1-2041.
Some background in Computational Geometry is needed in order to understand the material. Most of this background will be provided in class when it becomes relevant; in some cases though the students will be referred to specific pages in one of the Computational Geometry textbooks.
Most of the material is taken from recent papers and cannot be found in
There are several survey papers on geometric optimization and on specific topics in geometric optimization including the surveys by Agarwal and Sharir on geometric optimization, by Agarwal and Sen on randomized techniques for geometric optimization, by Arora on approximation schemes for NP-hard problems, and by Agarwal, Har-Peled and Varadarajan on approximation via corsets.
A recommended textbook in computational geometry is
Several home assignments will be given (four-six); students will participate in the presentation of the material; attendance is mandatory.
More precisely: homework – 60%, paper/topic presentation plus summary – 30%
Various topics in geometric optimization including
1. Parametric searching and related techniques
2. Center and median problems; clustering
3. Facility location optimization
4. Guarding and covering problems
5. Variants of the Euclidean TSP
6. Matching in geometric graphs
7. Applications in wireless networks (e.g., power assignment problems)
We will present both exact and approximate solutions for the problems above, emphasizing some of the general techniques that are used.
23.11.2010 Leonid + Roee The shifting strategy
25.11.2010 Vitali + Yakir A PTAS for Euclidean TSP
30.11.2010 Alon + Rotem G. TSP with weak triangle inequality
02.12.2010 Alla + Kiril k-center
14.12.2010 Or + Rom Local search
28.12.2010 Amir + Rotem M. Relay placement
06.01.2011 Anat + Yohai Optimizing network lifetime