Geometric Optimization (202-2-5311)
Prof.
Matya Katz
Fall 2010
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
textbooks.
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
Course requirements:
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