CS138 Computer Algorithms

Announcements

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.

Solutions to Homework 5: part 1, part 2.

Further reading:

  • Lecture notes from Oded Regev's course on lattices.
  • N.R. Devanur, C.H. Papadimitriou, A. Saberi and V.V. Vazirani, "Market Equilibrium via a Primal-Dual Algorithm for a Convex Program," Journal of ACM, vol. 55(5) (2008), link.

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):

  • S. Arora and S. Kale, "A Combinatorial, Primal-Dual approach to Semidefinite Programs," STOC 2007, link.
  • M. Laurent, "A comparison of the Sherali-Adams, Lovasz-Schrijver and Lasserre relaxations for 0-1 programming," Mathematics of Operations Research, vol. 28, pp.470-496, 2001, link.
  • G. Schoenebeck, L. Trevisan, and M. Tulsiani, "Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut," STOC 2007, link.
  • S. Khot, "On the power of unique 2-prover 1-round games," STOC 2002, link.
  • Lance Fortnow's blog post on the unique games conjecture --- has links to several related results, including hardness of approximation for Max Cut and Vertex Cover.

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 Firestone. Also, since we're going to miss some lectures, I'm trying to schedule an extra class on Friday.

Homework 5:

  • Vazirani, exercise 21.7 (bandwidth minimization) (15 points). Note, you can assume the result of exercise 21.6, to get the embedding of d into ell_2.
  • Vazirani, exercise 26.13 (vector program relaxation for k-coloring) (8 points).
  • Random number generators and the Chernoff bound (7 points). Let X be a sum of independent, identically distributed, binary-valued random variables. The Chernoff bound shows that X is sharply concentrated around its expectation value. Do you see the same behavior when you use your computer's random number generator, instead of "real" randomness? Try it and report your results.
This homework is due on Thursday, June 4. No extensions, so please start ahead of time--you're welcome to hand it in early. You can discuss in groups of up to 3, but please write up the solutions independently. You probably won't need any outside sources (e.g., books or the internet), but if you like, you can use them to look up basic facts. You cannot use sources that directly solve these problems. Chris and Euiwoong are both available for this homework (or you can always talk to me). Chris will take care of the first problem, and Euiwoong will take care of the last two.

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, 5.2, 5.3, due next Monday. For this homework, you can discuss in groups of up to 3, but please write up the solutions independently. Euiwoong is the TA for this homework (or you can always talk to me). UPDATE: 5.2 is not required, but you can hand it in for extra credit.

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 100 Powell-Booth (UPDATE: they kicked us out again!) 308 Firestone.

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. Due next Monday. (UPDATE: See above.)

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.

About this course

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:

COMBINATORIAL ALGORITHMS:
Solving Set Cover using a greedy algorithm (Ch. 2)
Steiner Tree and the Traveling Salesman Problem, via minimum spanning trees (Ch. 3)
The k-center problem (Ch. 5)
Shortest Superstring (Ch. 7)

ALGORITHMS BASED ON LINEAR PROGRAMMING:
Solving convex programs using the ellipsoid algorithm
LP duality, dual fitting (Ch. 12-13)
Set Cover, using LP rounding (Ch. 14)
Set Cover, using primal-dual schema (Ch. 15)
Steiner Forest (Ch. 22)

OTHER TOPICS:
Local search heuristics for the Traveling Salesman Problem; experimental studies of algorithms
Solving MAX-CUT via semidefinite programming (Ch. 26)
Lattice reduction and integer programming
Counting DNF solutions and network reliability (Ch. 28)