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

Homework Assignments:

Homework assignment no. 1, due November 2, 2010

Homework assignment no. 2, due November 16, 2010

Homework assignment no. 3, due December 7, 2010

Homework assignment no. 4, due January 6, 2011