WEEK 10 - Something old, something new: lattice basis reduction, with applications to integer programming and cryptography; algorithms for markets and bargaining.
Note: No class on Monday (I'll be at the STOC conference). Class on Wednesday, Homework 5 is due on Thursday, and I'll have an extra make-up lecture on Friday, 10-11:30am, in Moore 070. Then we're done... there is no final exam for this course.
WEEK 9 - Are there better algorithms for Vertex Cover and Max-Cut? Lovasz-Schrijver relaxations, the Unique Games Conjecture, and primal-dual SDP algorithms.
Note: No class on Monday (Memorial Day holiday). Wednesday, it seems, is Ditch Day. Also, no office hours on Friday (I'll be out of town).
Further reading (in case you're interested... we're only going to cover a small fraction of this material):
WEEK 8 - Sparsest cut (continued from last week); Max-Cut using semidefinite programming (Ch. 26)
Note: On Wednesday, we're meeting in a different location, 308
WEEK 7 - Multicut and integer multicommodity flow in trees (Ch. 18); sparsest cut (Ch. 21)
5/11/09 - Homework 4 is due (solutions). No new homework this week.
WEEK 6 - Scheduling on unrelated parallel machines (Ch. 17); practical performance of scheduling algorithms (Johnson, "A Theoretician's Guide to the Experimental Analysis of Algorithms," in "Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges," 2002, link; Savelsbergh, Uma and Wein, "An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems," INFORMS J. on Computing 17, pp.123-136, 2005, link)
5/4/09 - Homework 4: Vazirani, exercises 14.1, 14.2, 14.5, 15.3, due next Monday. These are shorter problems, so each one is worth 5 points. Please work by yourself this time. Euiwoong is the TA for this homework (or you can always talk to me).
WEEK 5 - Set cover using LP rounding, primal dual schema, dual fitting (Vazirani, Ch. 14, 15, 13); Max-SAT, derandomization via conditional expectations (Ch. 16)
4/27/09 - Homework 3 is due (solutions). No new homework this week. I just discovered that my copy of the textbook is an older printing than the one that most students have. Exercise 12.7 in my book is 12.8 in your book, and your 12.7 is my 12.6. I won't take off points for this.
WEEK 4 - Linear programming duality, network flow (Vazirani, Ch. 12); the ellipsoid method (sections 0, 1 and 2 in Grotschel, Lovasz and Schrijver, "The ellipsoid method and its consequences in combinatorial optimization," Combinatorica 1(2) (1981), pp.169-197 - link)
4/20/09 - Homework 2 is due (solutions -- sorry these are so terse, ask if you have trouble understanding them). Homework 3: Vazirani, exercises 11.2 and 12.7, due next Monday. (For 12.7, you can use these conditions which imply that a matrix is totally unimodular. Also, use Cramer's rule to write down the solution to a system of linear equations.) You may discuss in groups of up to 3, but please write up the solutions independently. Chris is the TA for this homework (or you can always talk to me).
WEEK 3 - Euclidean traveling salesman, PTAS's (Vazirani, Ch. 11); Johnson-Lindenstrauss lemma, metric embeddings (Matousek, Lectures on Discrete Geometry, sections 15.1, 15.2, and more if we have time (link)). See also Vempala, The Random Projection Method, Ch. 1 and the beginning of Ch. 3. Matousek and Vempala both discuss these topics; Matousek is available online, but a bit dense. Vempala is easier to follow, though sometimes a bit sketchy.
4/13/09 - Homework 1 is due (solutions).
Homework 2: Vazirani, exercises 3.6,
WEEK 2 - Steiner tree, traveling salesman, MST's (Vazirani, Ch. 3); k-Center and parametric pruning (Ch. 5)
4/8/09 - 4/10/09 - We actually got further ahead, and talked about k-Center and parametric pruning (Ch. 5)
4/6/09 - Class cancelled because of Student-Faculty Conference. I'll have a make-up lecture on Friday, 4/10, at 10-11:30, in 070 Moore.
WEEK 1 - Vertex cover, set cover, greedy algorithms (Vazirani, Ch. 1-2)
4/1/09 - I'll have office hours this Friday at 4-5pm in Steele, room 202D.
4/1/09 - Also, it's confirmed that we'll be meeting in 070 Moore from
now on, except for one day, Wednesday 5/20, when we'll be in
4/1/09 - Homework is now due the following Monday, 4/13. Textbook should be available from the bookstore this Friday, 4/3. General guidance about the homework: do the problems by yourself, write up proofs with the same level of rigor and detail as in the textbook. Please no late homework, unless you have a good reason and you let me know early.
3/30/09 - BTW, I forgot to say something in class, about the comparison between the two greedy algorithms for vertex cover. The "greedy vertex" algorithm achieves approximation ratio O(log n), while the "greedy matching" algorithm achieves approximation ratio 2. But the "greedy vertex" algorithm is still useful, because it does better than "greedy matching" in many cases, e.g., on the complete bipartite graph.
3/30/09 - Homework: Vazirani, exercises 2.1, 2.2, 2.5.
3/30/09 - Lectures moved again to Moore, room 070. Sorry for the confusion, we'll meet here for the rest of the quarter.
3/15/09 - Lectures moved to Powell-Booth, room 100.
Term: Spring 2009
Instructor: Yi-Kai Liu (yikailiu (at) caltech (dot) edu)
TA's: Chris Beck (cbeck (at) caltech (dot) edu) and Euiwoong Lee (woong315 (at) caltech (dot) edu)
Lectures: MW 10:00-11:25, in Moore, room 070
Office hours: Friday, 4-5pm, in Steele, room 202D
Textbook: Vazirani, Approximation Algorithms
This course will be about approximation algorithms for combinatorial optimization problems. It turns out that for many such problems, one can find near-optimal solutions efficiently, even though finding exactly optimal solutions is NP-hard. We will describe several techniques for designing approximation algorithms, including combinatorial methods and linear programming relaxations. This course will be mostly theoretical, focusing on polynomial-time algorithms with provable bounds on the approximation ratio. However, we may also talk a bit about heuristic methods that perform well in practice.
Here is a (tentative) list of topics:
ALGORITHMS BASED ON LINEAR PROGRAMMING: