CS 7520 - Approximation Algorithms

READING PROJECT

You have already been exposed to the main concepts in approximation algorithms and to the fundamental algorithmic techniques. The purpose of this project is to demonstrate that you understand the topic well enough, so that you can do independent reading and grasp and present the main ideas. You may work alone, or in groups of two.

Listed are suggested readings that touch in some depth on a topic/problem not discussed in class. Pick one, and prepare a few pages of comprehensible notes on what is the issue, and what are the main technical ideas. You should think of these notes as a write up that you would be posting, if you were to give a lecture on your chosen topic. The readings on each topic are just "suggested" readings. If you find other readings that you are more comfortable with, please go ahead. Also, you do not have to pick from the suggested list below. If there is another topic/problem that you would rather write about, you may certainly do so (though just check with the instructor via a short email, to be sure that your chosen topic/reading is appropriate).

You may want to take a look at all the proposed readings before you choose one. You may also want save this reading list for your future reference.

Euclidean TSP: In the mid 90's Sanjeev Arora gave a polynomial time approximation scheme for the traveling salesman problem, when the points are in Euclidean space, thus resolving a 20 year standing open problem in a surprizing direction (prior to Arora's PTAS, it was generally believed that Euclidean TSP should be roughly as hard as general metric TSP). Read Arora's algorithm in Chapter 11 of Vazirani's book. You may also want to read Arora's original Euclidean TSP paper which gives a lot of history, context, and technical details.

Iterated Rounding: In class we discussed iterated rounding. Instead of solving an LP and rounding, we repeatedly round only "part" of the fractional solution, and define a more refined LP, until an integral solution is obtained. Kamal Jain introduced this method in his novel factor 2 approximation algorithm for Steiner network. Recently, Mohit Singh and Lap Chi Lau gave a near optimal approximation algorithm for the bounded degree minimum cost spanning tree problem, also using iterated rounding. In class, Gagan Goel presented his joint work with Deeparnap Chakrabarty on budgeted allocations via randomized rounding. Read (a), (b) or (c) below (reading more than one is, of couse, also fine).
(a) Kamal Jain's algorithm in Chaper 23 of Vazirani's book.
(b) The algorithm of Singh and Lau on bounded degree MST.
(c) The algorithm of Chakrabarty and Goel on budgeted allocations.

Metric Distance Embeddings and Algorithms: Chandra Chekuri from UIUC, has excellent lecture notes on embedding finite metrics to tree metrics, with applications in approximation algorithms. Read Chekuri's lecture notes. You may also look at Yair Bartal's related paper and the applications and further references mentioned there.

Stochastic Optimization: It is natural that some parameters of an optimization problem are not fixed, but sampled from a distribution. For example, suppose that you have to cover a fixed set of elements using a fixed collection of sets. However, the sets will be bought from a certain "market", and their costs are not fixed, but will be determined at the time when they will be bought by sampling from a probability distribution. Read at least one of the papers of Dean, Goemans and Vondrak on stochastic knapsack, stochastic packing and stochastic covering. You may also find and read any other suitable paper on stochastic optimization. (a) Stochastic Knapsack. (b) Stochastic Packing . (c) Stochastic Covering .

Flow Algorithms based on Sampling: In class we saw Karger's novel sampling algorithm for mincut (and general small capacity cuts) and approximating network reliability. Karger and his collaborators have also given very fast flow algorithms, also based on sampling. Read one (or more) of Karger's super-fast flow algorithms. (a) Cuts and Flows in Capacitated Graphs. (b) Sampling in Residual Graphs.

On Positive Semidefinite Programming: In class we derived 0.87856 approximation algorithms for MAXCUT and MAX2SAT. We showed that these problems can be written as strict quadratic probrams whose relaxations are vector programs. We used as a black box that vector programs can be approximated efficiently up to arbitrary precision by positive semidefinite programs (just as we have used as a black box that linear programs can be solved in polynomial time), and proceeded to round the solutions of vector programs and produce integral solutions for MAXCUT and MAX2SAT with proven approximation factor 0.87856. Read the explanation of the reduction of vector programs to positive semidefinite programs, and the solution of the latter via separating hyperplanes and the ellipsoid method (paragraphs 26.2 and 22.3 in Vazirani's book). You may also read a wonderful survey by Michel Goemans on semidefinite programming, which goes more in depth on the origins of the method.

Sparsest Cut: In class we discussed the sparsest cut problem and sketched the novel algorithm of Leighton and Rao (1988) giving an order logn approximation (Chapter 21 in Vazirani's book). The Leighton-Rao approach goes through LPs and metric embeddings. In 2004, Arora, Rao and Vazirani (Umesh Vazirani) gave an order square-root logn approximation, using a semidefinite programming relaxation, and new embeddings in high dimentional geometry. Read the Arora, Rao and Vazirani paper.

Hardness of Approximations: Read Vazirani's Chaper 29 on hardness of approximations. You may also want to see Sanjeev Arora's survey which came right after the very first inapproximability results. Finally, this is not something that you have to read, but Arora and Barak just finished a wonderful book on a modern approach to complexity theory, which you can download from Complexity Book for a short while (until it is published).

Online Algorithms and Competitive Analysis: In many practical situations the input of an algorithm is not known in advance. The input comes in pieces "online", while the algorithm has to make irrevocable decisions without knowing the entire input which will come in the future. For example, if you have a small fast cache memory and a very large but slow memory, when an item is requested which is in the slow memory but not in the cache, you have to decide which item to evict from the cache in order to fetch the requested item, without knowing the future requests. Online algorithms is the study of methods which develop algorithms performing as close as possible to an optimal algorithm knowing the entire input in advance; this is called competitive analysis. Online algorithms can be thought of as approximation algorithms in a different computational scenario. Read the following survey articles of Susanne Albers on online algorithms and competitive analysis: Online Article I, Online Article II, Competitive Analysis.