• Instructor
• Overview
• Grading
• Lectures
• Homework
• Reading
• Links
• Participants

Combinatorial optimization typically deals with problems of optimizing an objective function subject to a number of constraints. In many applications, the objective function of the underlying optimization problem involves a small number of variables, and the constraints are induced by a family of geometric objects. These problems are referred to as geometric-optimization problems. In such cases one expects that the underlying geometry can be exploited to obtain faster and simpler algorithms.

This course will cover various general techniques that have been developed to solve geometric-optimization problems, and a number of specific problems will also be discussed. The topics covered in the course will include:

0. Introduction (0.5 lectures)

1. Linear programming (3.5 lectures): Brief overview of simplex, ellipsoid, and interior-point methods, duality, randomized algorithms, a subexponential algorithm and LP-type problems.

2. Parametric searching (3 lectures): Megiddo's technique, multidimensional parametric searching, variants of parameteric searching, randomized techniques.

3. eps-approximations and eps-nets (2 lectures): Range spaces, VC-dimension, combinatorial bounds and algorithms, discrepancy, streaming.

4. Core-sets (2 lectures): geometric sampling, eps-kernel, core-sets for polynomials and other functions, kinetic geometry, streaming model.

5. Geometric packing and covering (2 lectures): geometric set cover, geometric independent set, art gallery problem.

6. Shape fitting and Clustering (3 lectures): k-center, k-median, spectral clustering, projective clustering, clustering mobile data.

7. Network design (4 lectures): Euclidean TSP, Euclidean minimum weight matching, spanners, well separated pair decomposition, collision-free shortest paths.

8. Shape matching (2 lectures): Hausdorff distance, Frechet distance, iterative closest pair, earth mover's distance.

9. Embeddings (2 lectures): Johnson-Lindenstrauss lemma, probabilistic embedding into trees, embeddings into Euclidean spaces.

There is no textbook for this course.

Assignments: 30% weight

Four assignments will be given during the semester, which each student has to complete individually.

Scribe: 30% weight

Each student has to scribe roughly two lectures. Scribed notes should be completed individually, but you can certainly ask your peers to clarify any point that your notes leave unclear.

Research Project: 40% weight

The intention is to produce a work of publishable or near-publishable quality. It will consist of a comprehensive survey on a topic plus new research work.