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 minimumweight edge on the unique st 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 2approximation 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:301pm.
 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 graduatelevel, introductory course into approximation and randomized
algorithms. Many discrete optimization problems (arising in theory and practice) turn
out to be NPhard, 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
nearoptimal 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,
linearprogramming (LP) based methods (the primaldual method, deterministic and
randomized rounding of LP solutions), semidefiniteprogramming 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.
See below for a tentative list of topics, and
here for a pdf version of the course outline containing a
list of topics.

 May 7: Introduction. Started with set cover. The greedy algorithm and a combinatorial
analysis showing an H_{n}approximation (where H_{n} is
the nth 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 LProunding based Bapproximation 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: Primaldual algorithms for set cover. A Bapproximation 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 LProunding 4approximation algorithm  Section
4.5 of [WS] (improvements are described in Sections 5.8, 12.1 of [WS]). Started with the
JainVazirani primaldual algorithm  Section 7.6 of [WS], Chapter 24 of [V].
 May 16: Finished the JainVazirani algorithm. Defined the notion of a
Lagrangianmultiplier preserving (LMP) approximation algorithm. Sketched how an
LMP ρapproximation algorithm for UFL can be used to obtain a 2ρapproximation
algorithm for kfacility location (kFL)  Section 7.7 of [WS], Chapter 25
of [V]; both of these consider the special case of the kmedian problem.
 May 21: Finished the description and analysis of the 2ρapproximation algorithm
for kFL using an LMP ρapproximation algorithm for UFL. Localsearch based
5approximation algorithm for kmedian  Section 9.2 of [WS].
 May 23: Started with network connectivity problems. Classes of cutrequirement
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 primaldual algorithm for {0,1}proper (and downwardsmonotone) functions.
 May 28: Completed the description of the primaldual algorithm and showed that it is a
2approximation 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 primaldual schema for network connectivity problems is due to Goemans and
Williamson. Here is a survey by them;
Sections 4.1, 4.34.6 are particularly relevant. Here is their original paper:
"A General Approximation Technique for
Constrained Forest Problems", SIAM Journal on Computing, 24:296317, 1995.
Defined structured classes of non{0,1} cutrequirement functions.
 May 30: Started with Jain's iterative rounding algorithm for network design with
general weakly supermodular cutrequirement 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
cutcovering 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 iterativerounding algorithm and proved that it yields a
2approximation. 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
cutcovering LP with weakly supermodular functions. The proof of Theorem 11.21 in Section
11.3 of [WS] uses the fractionaltoken counting argument discussed in class, although the
argument therein is more elaborate because they do not perform the same rowoperations to
simplify the matrix. The proof of Theorem 23.6 in Chapter 23 of [V] uses a different
counting argument. Started with the mincost boundeddegree spanning tree (MBDST) problem.
 Jun 6: LPrelaxation 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 cutrequirement LP for SNDP and MBDST LP can be
obtained via minimum st cut computations  Sections 11.2, 11.3 of [WS].
Chapter 7 of [KT] contains a good treatment of the min st cut and its dual
max st 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 KargerKleinTarjan. Described the
building blocks of Boruvka phases, Fheavy 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 Mincut due to Karger based on
contracting random edges  Section 10.2 of [MR].
 Jun 18: Described and analyzed a faster mincut algorithm based on recursive
application of the simple contraction algorithm  Section 10.2.2 of [MR]. Randomized
rounding for the minimum st cut problem dhowing the integrality of the
min st cut LP.
 Jun 20: Multiway cut  LP relaxation and a 1.5approximation algorithm based on
LProunding  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 regiongrowing technique and the resulting
approximation algorithm  Section 8.3 of [WS], Chapter 20 of [V]. Application of
regiongrowing 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 divideandconquer algorithm for the mincut
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
buyatbulk network design problem  Section 8.6.
 Jul 2: Defined l_{1} 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_{1} metrics
and weighted cut metrics. Started with the result showing that every npoint 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 treeembedding 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 treeembedding
result. Started with the construction showing that an npoint metric can be
embedded into l_{1} with O(log n) distortion 
Section 15.1 of [WS], Section 21.4 of [V]. Discussed distancebased 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^{3} n), dimensions.)
 Jul 11: Finished the l_{1}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_{2})^{2}metrics and the
semidefiniteprogramming (SDP) relaxation for sparsest cut, and the resulting improved
result for sparsest cut due to AroraRaoVazirani (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 cuttree packings, and the resulting treebased obliviousrouting scheme,
and formulated an LP to find a cuttree packing that yields an obliviousrouting scheme
with low congestion.
 Jul 18: Finished with the cuttree packing result that yields
an O(log n)competitive obliviousrouting 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 cutrelated problems  Section 15.3 of
[WS]. Described and analysed the SDPbased approximation algorithm for MaxCut  Sections
16.1, 16.2 of [WS], Sections 26.126.4 of [V].
 Jul 23: Started with the Lovasz Local Lemma (LLL). Gave a nonconstructive proof and
its application to kSAT  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 kSAT problem; this predates the MoserTardos algorithm. Described the
MoserTardos (MT) algorithm giving a constructive proof of LLL and started with its
analysis.
Here is the MoserTardos 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 jobshop scheduling. For references on the jobscheduling application, see the survey
"Approximation algorithms for scheduling" by Leslie Hall, which appears as Chapter 1 of
the book "Approximation Algorithms for NPHard 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.
We will supplement the above texts with various research papers, notes etc., as necessary,
which will be posted online. The following text on algorithm design has also been placed
on reserve at the Davis Center library, and is a useful reference for some topics related
to algorithm design.
 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, primaldual methods.
 Facility location. Localsearch, LProunding, primaldual methods.
 Network Design. Cutcovering problems and the primaldual schema. Iterative rounding
methods and applications to survivable network design and degreebounded network
design.
 Two gems in randomized algorithms. Karger's mincut algorithm, and the
KargerKleinTarjan lineartime minimumspanningtree algorithm.
 Cut problems. LProunding algorithms for multiway cut, multicut, sparsest cut, and
their applications.
 Metric embeddings: L1embeddings, FRT trees and their applications.
 Cuttree packings: Räcke trees and their connection with FRT trees.
 Semidefiniteprogramming relaxations: maxcut 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.
