CO759: Approximation and Randomized Algorithms
(Topics in Discrete Optimization)

Announcements (assignments etc.)

• Aug 7: The "Topics covered" section has been updated.
• Jul 28: Assignment 3 is available.
  Due by Aug 12, 2013.
• Jul 25: There was a typo in Q4(a): in the algorithm, e_s,t is the minimum-weight edge on the unique s-t path in H.
  Q4(c) had a more serious potential mistake: the statement that for every extreme point x, there is some e with x_e at least 0.5 could be incorrect. The proof I had in mind does not work, but I don't yet have a counterexample. I apologize for this mistake. A 2-approximation algorithm for multicut on trees can be obtained even without this property. The assignment below has been updated.
• Jul 11: My office hours today have been moved to Friday, Jul 12 from 11:30-1pm.
• Jul 4: Assignment 2 is available. Updated Jul 25.
  Due by Jul 23 Jul 25, 2013.
• Jun 13: There was an error in Q4(b) of the assignment. The question asked you to prove an incorrect statement, which has now been corrected. Also, the hint in Q1(c) has been clarified to say that the "cost of the sets" used by the greedy algorithm to cover k remaining uncovered elements is at most k.
• May 29: Assignment 1 is available. Updated Jun 13.
  Due by Jun 20, 2013.
• May 6: Welcome to CO 759.

Course Overview and Outline

This is a graduate-level, introductory course into approximation and randomized algorithms. Many discrete optimization problems (arising in theory and practice) turn out to be NP-hard, and thus optimal solutions cannot be computed unless P=NP. One approach to deal with this situation is to design an approximation algorithm for the problem, that is, an efficient algorithm that is guaranteed to return a provably near-optimal solution. Over the past three decades, the theory of approximation algorithms has blossomed into a beautiful and powerful theory with deep and interesting connections to mathematical programming and analysis. The course will study some of the successful paradigms for designing approximation algorithms such as greedy methods, linear-programming (LP) based methods (the primal-dual method, deterministic and randomized rounding of LP solutions), semidefinite-programming relaxations, approximation of metrics. Randomization turns out to be an extremely useful idea in the design of approximation algorithms, and algorithms in general. We will also study some key tools in probability and their applications in the design of algorithms.

Topics Covered (including relevant references)

• May 7: Introduction. Started with set cover. The greedy algorithm and a combinatorial analysis showing an H_n-approximation (where H_n is the n-th harmonic number) - Theorem 1.11 in [WS], Section 2.1 of [V]. The use of LPs in the design of approximation algorithms - Chapter 1 of [WS], Chapter 12 of [V]. Appendix [A] on [WS], Chapter 12 of [V] give a primer on linear programming. An LP-rounding based B-approximation algorithm, and an O(ln n)-approximation algorithm using randomized rounding - Sections 1.3, 1.7 of [WS], Sections 14.1, 14.2 of [V].
• May 9: Primal-dual algorithms for set cover. A B-approximation algorithm via maximal dual feasible solutions - Sections 1.4, 1.5 of [WS] and Section 15.2 of [V] describe various ways of obtaining a maximal dual feasible solution. An H_Δ-approximation algorithm - Theorem 1.12 in [WS], Section 13.1 of [V]. The idea of constructing a feasible dual by taking an infeasible dual and scaling it is sometimes called "dual fitting"; we will not be particular about this distinction. Started with uncapacitated facility location problem (UFL).
• May 14: Started with metric UFL. Gave an LP relaxation, and some economic motivation for the dual LP - Section 4.5 of [WS]. An LP-rounding 4-approximation algorithm - Section 4.5 of [WS] (improvements are described in Sections 5.8, 12.1 of [WS]). Started with the Jain-Vazirani primal-dual algorithm - Section 7.6 of [WS], Chapter 24 of [V].
• May 16: Finished the Jain-Vazirani algorithm. Defined the notion of a Lagrangian-multiplier preserving (LMP) approximation algorithm. Sketched how an LMP ρ-approximation algorithm for UFL can be used to obtain a 2ρ-approximation algorithm for k-facility location (k-FL) - Section 7.7 of [WS], Chapter 25 of [V]; both of these consider the special case of the k-median problem.
• May 21: Finished the description and analysis of the 2ρ-approximation algorithm for k-FL using an LMP ρ-approximation algorithm for UFL. Local-search based 5-approximation algorithm for k-median - Section 9.2 of [WS].
• May 23: Started with network connectivity problems. Classes of cut-requirement functions and their use in modeling various network connectivity problems. Gave an LP relaxation and some motivation for the dual LP. Here are the slides used in this lecture. Sketched the primal-dual algorithm for {0,1}-proper (and downwards-monotone) functions.
• May 28: Completed the description of the primal-dual algorithm and showed that it is a 2-approximation for {0,1}-proper functions. Section 7.4 of [WS], and Chapter 22 of [V] describe essentially the same algorithm, but this is stated and analyzed for the special case of the Generalized Steiner tree (also called Steiner forest) problem. The primal-dual schema for network connectivity problems is due to Goemans and Williamson. Here is a survey by them; Sections 4.1, 4.3-4.6 are particularly relevant. Here is their original paper: "A General Approximation Technique for Constrained Forest Problems", SIAM Journal on Computing, 24:296-317, 1995. Defined structured classes of non-{0,1} cut-requirement functions.
• May 30: Started with Jain's iterative rounding algorithm for network design with general weakly supermodular cut-requirement functions, which includes the survivable network design problem (SNDP) as a special case - Section 11.3 of [WS], Chapter 23 of [V]. Stated facts about extreme points of general LPs. These and other related properties of extreme points can be founded in any standard text on linear programming and/or polyhedral theory such as "Linear Programming" by Vasek Chvátal, "Combinatorial Optimization" by Christos Papadimitriou and Kenneth Steiglitz.
  Stated the structural property that an extreme point x of the cut-covering LP with weakly supermodular functions is defined by a laminar family, and that this implies that there is some edge e with x_e ≥ 0.5. Described the iterative-rounding algorithm and proved that it yields a 2-approximation. Started with the proof that an extreme point has some coordinate whose value is at least 0.5.
• Jun 4: Finished proving properties of extreme points for the cut-covering LP with weakly supermodular functions. The proof of Theorem 11.21 in Section 11.3 of [WS] uses the fractional-token counting argument discussed in class, although the argument therein is more elaborate because they do not perform the same row-operations to simplify the matrix. The proof of Theorem 23.6 in Chapter 23 of [V] uses a different counting argument. Started with the min-cost bounded-degree spanning tree (MBDST) problem.
• Jun 6: LP-relaxation for MBDST, properties of extreme points of the LP, and Singh and Lau's iterative algorithm for MBDST - Section 11.2 of [WS].
• Jun 11: Discussed the ellipsoid algorithm briefly, stated the concept of a separation oracle, and the equivalence of separation and optimization - Section 4.3 of [WS]. Stated that a separation oracle for the cut-requirement LP for SNDP and MBDST LP can be obtained via minimum s-t cut computations - Sections 11.2, 11.3 of [WS]. Chapter 7 of [KT] contains a good treatment of the min s-t cut and its dual max s-t flow problems.
  Here are the slides used for the ellipsoid method. The definitive reference for the ellipsoid method is "Geometric Algorithms and Combinatorial Optimization" by Martin Grötschel, László Lovász, and Alexander Schrijver. Here is a survey by Bland, Goldfarb, and Todd.
  Randomized linear time algorithm for MST due to Karger-Klein-Tarjan. Described the building blocks of Boruvka phases, F-heavy edges - Section 10.3 of [MR].
• Jun 13: Finished the description and analysis of the randomized algorithm for MST. Described a simple randomized algorithm for Min-cut due to Karger based on contracting random edges - Section 10.2 of [MR].
• Jun 18: Described and analyzed a faster min-cut algorithm based on recursive application of the simple contraction algorithm - Section 10.2.2 of [MR]. Randomized rounding for the minimum s-t cut problem dhowing the integrality of the min s-t cut LP.
• Jun 20: Multiway cut - LP relaxation and a 1.5-approximation algorithm based on LP-rounding - Section 8.2; see also Sections 19.1 and 19.2 of [V] which present a slight variation of the algorithm discussed in class having the same approximation guarantee.
• Jun 25: Multicut - LP relaxation, the region-growing technique and the resulting approximation algorithm - Section 8.3 of [WS], Chapter 20 of [V]. Application of region-growing to finding a balanced cut of cost O(log n) times the value of the optimal bisection - Section 8.4.
• Jun 27: Using balanced cuts to give a divide-and-conquer algorithm for the min-cut linear arrangement problem - Section 21.6.4 of [V]. Started with cuts, metrics, and tree embeddings. Defined tree embeddings and showed how this can be useful by considering the buy-at-bulk network design problem - Section 8.6.
• Jul 2: Defined l₁ metrics, (weighted) cut metrics, tree metrics, the concept of embedding one metric into another metric or a convex combination of metrics -see Section 21.3 of [V] for the equivalence between l₁ metrics and weighted cut metrics. Started with the result showing that every n-point metric can be embedded into a convex combination of dominating tree metrics with O(log n) expected distortion - Section 8.5 of [WS].
• Jul 4: Finished the randomized tree-embedding result. Started with the construction of a single tree metric that approximates "volumes" within an O(log n) factor - Theorem 8.25 in [WS].
• Jul 9: Finished the construction and analysis of the deterministic tree-embedding result. Started with the construction showing that an n-point metric can be embedded into l₁ with O(log n) distortion - Section 15.1 of [WS], Section 21.4 of [V]. Discussed distance-based embeddings (which are called Fréchet embeddings) and the properties that one wants from these to get the desired result. See also the following excellent notes by Luca Trevisan to get good intuition about the result. (The construction described in his notes uses slightly more, O(log³ n), dimensions.)
• Jul 11: Finished the l₁-embeddings result, and showed how this leads to an O(log n)-approximation algorithm for sparsest cut - Section 15.1 of [WS], Chapter 21 of [V].
• Jul 16: Briefly discussed (l₂)²-metrics and the semidefinite-programming (SDP) relaxation for sparsest cut, and the resulting improved result for sparsest cut due to Arora-Rao-Vazirani (ARV) - see Section 15.4 of [WS] for a detailed description and analysis of the ARV algorithm. Started with tree embeddings for cuts (also called Räcke trees) and oblivious routing - Section 15.2 of [WS]. Described cut-tree packings, and the resulting tree-based oblivious-routing scheme, and formulated an LP to find a cut-tree packing that yields an oblivious-routing scheme with low congestion.
• Jul 18: Finished with the cut-tree packing result that yields an O(log n)-competitive oblivious-routing scheme. Showed that this yields an embeddings for cuts of a graph that preserves cuts within an O(log n) factor, which in turn leads to O(log n)-approximation for various cut-related problems - Section 15.3 of [WS]. Described and analysed the SDP-based approximation algorithm for Max-Cut - Sections 16.1, 16.2 of [WS], Sections 26.1-26.4 of [V].
• Jul 23: Started with the Lovasz Local Lemma (LLL). Gave a non-constructive proof and its application to k-SAT - Section 5.5 of [MR]. This also describes an algorithm to construct a satisfying assignment, that is, a constructive proof of LLL tailored for the k-SAT problem; this predates the Moser-Tardos algorithm. Described the Moser-Tardos (MT) algorithm giving a constructive proof of LLL and started with its analysis.
  Here is the Moser-Tardos paper: "A Constructive Proof of the General Lovász Local Lemma", JACM, 57(2): 2010.
  See also the paper: "New Constructive Aspects of the Lovász Local Lemma", by Haeupler, Saha, and Srinivasan, which further expands the scope of the MT algorithm.
• Jul 25: Finished with the proof of the MT algorithm. Briefly discussed an application to job-shop scheduling. For references on the job-scheduling application, see the survey "Approximation algorithms for scheduling" by Leslie Hall, which appears as Chapter 1 of the book "Approximation Algorithms for NP-Hard Problems," edited by Dorit Hochbaum; PWS Publishing, 1995.

Prerequisites

There is no official prerequisite for the course. I will assume some basic knowledge of graphs, algorithms, and optimization. A course in algorithms (at the undergraduate level) might be useful but is not essential. If you would like to take the course but are unsure about the prerequisites, then come and talk to me.

Books and Supplementary Material

We will use the following books as references

• The Design of Approximation Algorithms by David Williamson and David Shmoys. Cambridge University Press, 2011.
  Referred to as [WS] in Topics Covered. Thanks to the publishers, this book can also be viewed online here.
• Approximation Algorithms by Vijay Vazirani. Springer, 2003.
  Referred to as [V] in Topics Covered. Placed on reserve at the Davis Center library.
• Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan. Cambridge University Press, 1995.
  Referred to as [MR] in Topics Covered. Placed on reserve at the Davis Center library.

• Algorithm Design by Jon Kleinberg and Eva Tardos. Addison Wesley, 2005.
  Referred to as [KT] in Topics Covered.

Collaboration Policy

Students are allowed to collaborate on the assignments to the extent of formulating ideas as a group. Each student is expected to write up the solutions by himself or herself. All hints, collaboration, outside help etc. should be explicitly listed in your submission.

Tentative list of topics

Some subset of the following topics will be covered. This is a course that offers plenty of flexibility. If there is a topic that is not in here and you would really like to see covered, come and talk to me about it!

• Set cover. The greedy algorithm, randomized rounding, primal-dual methods.
• Facility location. Local-search, LP-rounding, primal-dual methods.
• Network Design. Cut-covering problems and the primal-dual schema. Iterative rounding methods and applications to survivable network design and degree-bounded network design.
• Two gems in randomized algorithms. Karger's min-cut algorithm, and the Karger-Klein-Tarjan linear-time minimum-spanning-tree algorithm.
• Cut problems. LP-rounding algorithms for multiway cut, multicut, sparsest cut, and their applications.
• Metric embeddings: L1-embeddings, FRT trees and their applications.
• Cut-tree packings: Räcke trees and their connection with FRT trees.
• Semidefinite-programming relaxations: max-cut and sparsest cut.
• The Lovász local lemma and its applications.
• Counting problems: random walks and their applications.
• The unique games conjecture. Raghavendra's result.