CS138 Computer AlgorithmsAnnouncementsWEEK 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 makeup lecture on Friday, 1011:30am, in Moore 070. Then we're done... there is no final exam for this course. Solutions to Homework 5: part 1, part 2. Further reading:
WEEK 9  Are there better algorithms for Vertex Cover and MaxCut? LovaszSchrijver relaxations, the Unique Games Conjecture, and primaldual 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); MaxCut using semidefinite programming (Ch. 26) Note: On Wednesday, we're meeting in a different location, 308
Firestone. Homework 5:
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 LPBased Approximation Algorithms for Scheduling Problems," INFORMS J. on Computing 17, pp.123136, 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); MaxSAT, 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.169197  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); JohnsonLindenstrauss 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); kCenter and parametric pruning (Ch. 5) 4/8/09  4/10/09  We actually got further ahead, and talked about kCenter and parametric pruning (Ch. 5) 4/6/09  Class cancelled because of StudentFaculty Conference. I'll have a makeup lecture on Friday, 4/10, at 1011:30, in 070 Moore. WEEK 1  Vertex cover, set cover, greedy algorithms (Vazirani, Ch. 12) 4/1/09  I'll have office hours this Friday at 45pm 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 PowellBooth, room 100. About this courseTerm: Spring 2009 Instructor: YiKai 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:0011:25, in Moore, room 070 Office hours: Friday, 45pm, 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 nearoptimal solutions efficiently, even though finding exactly optimal solutions is NPhard. We will describe several techniques for designing approximation algorithms, including combinatorial methods and linear programming relaxations. This course will be mostly theoretical, focusing on polynomialtime 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: COMBINATORIAL ALGORITHMS:
ALGORITHMS BASED ON LINEAR PROGRAMMING:
OTHER TOPICS:
