CO453: Network Design
Winter 2007
MC 4033 ext. 33600
cswamy AT math DOT uwaterloo DOT ca
Time: MWF 1:30-2:20pm
Location: MC 4058
Office Hours: Wednesdays after class till 3:30pm and MWF 1:30-2:20pm from April 3-April 10.
Announcements
- Jan 3: Welcome to CO 453.
- Jan 5: There will be NO CLASS on Monday Jan. 8, as I will be out of town. I might hold
a makeup lecture
some time later in the course.
- Jan 12: Assignment 1 is available. Due on Wednesday, Jan. 24, 2007.
Here are the Solutions.
- Jan 22: CO 453 Midterm is scheduled for Wednesday, Feb. 14, 6-8pm in room MC 4058.
- Jan 25: Assignment 2 is available. Due on Friday, Feb. 2, 2007.
Here are the Solutions.
- Jan 30: Clarification in Question 1b): by "some MCA", I mean some MCA rooted at r. There
is a small
typo in Question 4c): it should be "u not equal to v" in the definition of cross
monotonicity. The assignment
has been updated.
- Feb 03: Assignment 3 is available. Due on Monday, Feb. 12, 2007.
Here are the Solutions.
- Feb 05: Typo in the assignment: in the definition of a proper function, in (iii) it should be
"f(A)=1 or f(B)=1".
This has been corrected. Another typo: in Question 3(b)
we contract the components of F", not F to form the
nodes of H; F" is the set
of edges added by the algorithm by that stage. This has also been corrected.
- Feb 10: Solutions to assignments 2 and 3 have been put up (see above).
- Feb 10: The syllabus for the midterm is everything covered up to the lecture on Feb 7 and
assignment 3.
This includes shortest paths, MSTs, mininmum-cost arborescences, NP-completeness,
approximation algorithms:
the 2-approximation algorithms for Steiner tree, 0-1 proper functions,
and 0-1 downwards-monotone functions.
- Feb 11: The Books and Supplementary Material section has been updated. Some
reference materials have
been posted there, and in the Topics Covered section
(see Feb 7).
- Feb 28: Here are the midterm solutions.
- Mar 3: Assignment 4 is available. Due on Monday, March 12, 2007.
Here are the Solutions.
- Mar 3: CO 453 Final is scheduled for Tuesday, April 10, 12:30-3pm in room RCH 206.
- Mar 7: Typo in Q1, it should be "min \sum_S w_Sx_S" instead of "max \sum_S w_Sx_S".
Clarification in Q2:
the graph G is a tournament. The assignment has been updated.
- Mar 7: CO 453 Makeup Midterm is scheduled for Thursday, March 15, 5-7pm in room MC 4058.
The syllabus includes everything up to (and including) the set-cover problem, that is, up to the lecture
on Feb 16
(excluding the portion on UFL) and Assignment 4.
- Mar 9: A couple more typos in the assignment. In 3a) it should be "weight of covered elements is at
least
0.5\sum_{e\in U}w_e" (this shows that the algorithm is a randomized 0.5-approximation algorithm).
In the
inequalities listed after 3b), the second inequality is valid if (\sum_{i=1}^k y_i) \in [0,1]. The assignment
has been
updated.
- Mar 12: Solutions to assignment 4 have been put up. There will be an in-class review session on Wednesday,
March 14, where I will go over the primal-dual algorithm for network connectivity with 0-1 proper functions.
- Mar 19: Assignment 5 is available. Due on Monday, March 26, 2007.
Here are the Solutions.
- Mar 25: Here are the solutions to the makeup midterm.
- Mar 26: Assignment 6 is available. Due on Monday, April 2, 2007.
Here are the Solutions.
- Apr 2: The syllabus for the final is everything covered after the first midterm (set cover, facility
location and its
variant with penalties, mechanism design), and MSTs, network connectivity for 0-1 proper and
0-1 downwards
monotone functions, from before the first midterm.
You should also know the definitions of the shortest-path and
minimum-cost arborescence (MCA) problems, and know
how to run Dijkstra's and Edmonds' algorithms. You
will not however be asked to prove properties about shortest
paths or MCAs or design algorithms for these
problems.
- Apr 2: From April 3 to April 10, I will hold extra office hours during the regular lecture timeslot.
- Apr 10: The final exam is scheduled for today at 12:30 in room RCH 206.
Your assignments 5 and 6 have been graded and I will be bringing them with me to the final exam.
If you would
like to know your grade earlier, then send me email, or check if I am in the office.
- Apr 10: There were a few typos in the solutions to assignments 5 and 6, which might have
caused some confusion.
In the solution to bonus problem 3 on assignment 5, in the Initialization
phase of the algorithm, C denotes the
set of "unprocessed" clients, that is, for
every client not in C, we have either tentatively assigned the client
to a
tentatively-open facility or have tentatively decided to incur penalty for it.
Also, a clarification: in step (b) of the Primal-Dual process, if
α>cij then we also remove j from C (this
would happen anyway in the next iteration, because event (a) would kick in).
In the solution to problem 2(b) on assignment 6, it should say "the algorithm f picks a set S'
iff x*S'>0".
These have been corrected. Sorry for any confusion.
- Jan 3: Course Introduction. Shortest paths: Dijkstra's algorithm - Section 4.4 of [KT].
- Jan 5: Finished shortest paths. Minimum spanning trees (MSTs): Prim's algorithm - Section 4.5 of [KT].
- Jan 8: No class.
- Jan 10: Finished Prim's algorithm. Kruskal's algorithm - Sections 4.5, 4.6 of [KT].
- Jan 12: A clustering application - Section 4.7 of [KT]. Started minimum cost arborescences -
Section 4.9
of [KT].
- Jan 15: Class cancelled because of UW closure.
- Jan 17: Finished minimum cost arborescences.
- Jan 19: Introduction to computational complexity - Chapter 8 of [KT]. Decision problems and
polynomial-
time reductions - Section 8.1 of [KT].
- Jan 22: The classes P, NP and NP-completeness - Section 8.3 of [KT]. Showed that 3-SAT, Set Cover,
and Steiner tree are in NP.
- Jan 24: Proved that Set Cover is NP-complete via a reduction from 3-SAT - Sections 8.1, 8.2 of [KT].
Proved that Steiner tree is NP-complete by reducing Set Cover to it. Sections 8.4-8.7 of [KT] contain
many
more NP-completness proofs via reductions.
- Jan 26: Gave a 2-approximation algorithm for minimum Steiner tree based on shortcutting an MST in the
metric completion of original instance - Section 3.1 of [V]. Introduced the general paradigm for
the design
and analysis of approximation algorithms. See Section 1.1 of [V].
- Jan 29: Talked about how linear programming (LP) relaxations of integer programs can be used to
obtain
lower bounds. Described the LP relaxation of the Steiner tree problem and obtained the
dual LP. Proved
weak duality, and stated strong duality, complementary slackness (CS) conditions.
Discussed the two
common ways in which LPs are used in approximation algorithms design and analysis:
(i) primal-dual
algorithms, (ii) LP-rounding algorithms. See Chapter 12 of [V] for a discussion of
these and related
topics like integrality gap.
- Jan 31: Gave a combinatorial and economic intuition for the dual lower bound for the Steiner tree LP.
Stated the various design rules used to obtain a primal-dual algorithm.
- Feb 2: Decribed the primal-dual algorithm for Steiner tree. Proved that under a certain lemma, which
can
be viewed as a suitable relaxation of the CS conditions, the algorithm is a 2-approximation algorithm
-
Chapter 22 of [V]. This chapter considers a more general problem, the Steiner forest problem, which
we
will cover on Feb 7.
Here are the slides used for some of this lecture and the previous one.
- Feb 5: Finished proof of lemma for Steiner tree. Started with modeling network connectivity problems
with 0-1 proper functions.
- Feb 7: Finished proof that the primal-dual algorithm for network connectivity with 0-1 proper functions is
a
2-approximation algorithm.
The primal-dual schema for network connectivity problems is due to Goemans and Williamson. Here is a
survey by them
(Chapter 4 in the book "Approximation Algorithms for NP-Hard Problems" listed below).
This contains much more than what we covered in class and is at a little higher level.
Sections 4.1, 4.3-4.6
are particularly relevant. The survey also contains some excercises.
Here is their original paper:
"A General Approximation Technique for Constrained Forest Problems",
SIAM Journal on Computing, 24:296-317, 1995.
- Feb 9: Started the set cover problem. Gave a primal-dual B-approximation algorithm where B
is the
maximum number of sets an element appears in - Section 15.2 of [V].
- Feb 12: Gave a primal-dual HΔ-approximation algorithm analyzed using dual fitting,
where Δ is the
maximum size of a set and Hk is the k-th harmonic number -
Section 13.1 of [V]. See also Section 2.1 of [V]
which gives the same algorithm, but stated
and analyzed as a natural greedy algorithm without any reference
to a primal or dual. Hence, we will
refer to this approximation algorithm as "the greedy algorithm".
Started with LP-rounding algorithms for set cover - Chapter 14 of [V]. Gave an LP-rounding based
B-approximation algorithm - Section 14.1 of [V].
- Feb 14: Gave an O(ln n)-approximation algorithm for set cover using randomized rounding -
Section 14.2 of
[V].
- Feb 16: Showed how one can slightly modify the randomized-rounding algorithm to obtain
an algorithm
that always returns a set cover and has the same O(ln n) performance guarantee.
Started with the
uncapacitated facililty location (UFL) problem with arbitary assignment costs.
Gave an LP relaxation, and
economic motivation for the dual LP - Section 24.1 of [V].
- Feb 26: Gave an LP-rounding O(ln n)-approximation algorithm for UFL with arbitrary assignment
costs, by
reducing the problem to set cover, and using duality and complementary slackness.
- Feb 28: Started UFL with metric assignment costs (metric UFL). Stated an LP-rounding algorithm based
on
clustering facilities around certain "hub"-clients.
- Mar 2: Class cancelled because of UW closure.
- Mar 5: Proved that the LP-rounding algorithm is a 4-approximation algorithm via complementary
slackness.
Extended the LP-rounding algorithm to metric UFL with penalties, and proved the same
approximation ratio.
- Mar 7: Started with the Jain-Vazirani primal-dual algorithm for UFL - Chapter 24 of [V].
- Mar 9: Completed description of primal-dual algorithm and proved an approximation ratio of 3 -
Section
24.4 of [V].
- Mar 12: Gave an overview of the ellipsoid algorithm for solving linear programs in polynomial time.
- Mar 14: Review session.
- Mar 16: Started with algorithmic mechanism design. Described informally the basic setup. Considered
the
single-item auction setup and how the auction can be seen as a method for finding the maximum of n
numbers
in an environment where the values of these numbers are held by n rational players who may
not reveal the
(true) values.
Described the first-price and second-price auctions. Proved that in the second-price auction, it
is always in the best interest of each player to reveal its true value.
- Mar 19: Described formally the mechanism-design setup and the basic questions that we will be
considering:
"given a target function g, do there exist payments/prices that implement g truthfully"?
Or if g arises as the
solution to some (NP-hard) optimization problem, one can ask "is there an
efficient approximation algorithm
f for the problem and payments/prices that truthfully
implement f"?
- Mar 21: Described a truthful mechanism for the shortest-path problem, where each edge is a player
whose
private value is the cost of the edge. Showed how one can obtain payments that when combined with
Dijsktra's algorithm yield a truthful mechanism, and under certain assumptions, also ensure that the
utility of
every player is non-negative if he reveals his true value.
- Mar 23: Described the VCG mechanism, and showed that the mechanism for the shortest path problem
follows as a special case.
- Mar 26: Defined single-dimensional domains. Proved a necessary condition for the truthful implementation
of a target function g.
- Mar 28: Simplified the necessary condition for truthful implementation to obtain a more compact necessary
monotonicity condition for truthful implementation of a target function g when the players' domains are
single-
dimensional. Proved that this necessary condition is also sufficient.
- Mar 30: Considered the set cover problem, where each set is a player whose private value is the weight
of
the set. For this single-dimensional domain, showed that the primal-dual B-approximation and
HΔ-approximation algorithms satisfy the desired monotonicity property.
- Apr 2: Considered the facility location problem, where each facility is a player whose private value is
its
facility opening cost. Showed that the Jain-Vazirani primal-dual algorithm satisfies the monotonicity
property.
Course Overview
A course on the design and analysis of algorithms for a broad class of problems
known as network design problems.
Many of the optimization problems that we will
study will be computationally intractable, and we will tackle these
problems by
designing approximation algorithms. We will study various techniques for the design and
analysis
of approximation algorithms via the lens of network design problems.
Three broad classes of problems that
we will consider are:
(a) Network connectivity problems, which typically entail constructing a
minimum-cost subgraph of an underlying
network that possesses certain desired
connectivity properties. Examples include shortest paths, minimum spanning
trees,
minimum Steiner trees, generalized Steiner forests;
(b) Location problems, that deal with the optimal placement of "facilities" at the
nodes of a network. A prototypical
example is the uncapacitated facility location
problem;
(c) Games on networks, where certain inputs to the problem are controlled by
self-interested rational agents. We
will study game versions of some of the above
problems, e.g., the minimum spanning/Steiner tree problem where the
edges or the
terminal vertices represent strategic players.
Prerequisites
The official prerequisites are: (MATH 239/249 and CO 350/CO 352/CM 340) or CO 355.
If you do not satisfy these prerequisites but are interested in taking this course for
credit, come and talk to me.
I will assume that you have some basic knowledge about graphs like basic terminology,
notation, concepts and
algorithms (some pointers to refresh your memory about graphs
are given below). I will devote a lecture or two
to linear programming and duality (in the
context of network design problems), which should be accessible even
if you have
never seen linear programs before.
A background in algorithms might be useful but is not essential.
Assignments and Exams
There will be 5 or 6 assignments that will be handed out roughly once every two
weeks, and will be due in two
weeks time. Late assignments will not be accepted.
You are encouraged to discuss the assignments with each other, but you must write up
the final solution
individually. You must also write down the names of all
your collaborators on the assignment (this does not
affect your mark).
Students suspected of cheating will automatically be assigned a zero mark on all
previous assignments, including
the assignment in question, and will be referred
to the Undergraduate Associate Dean.
The weightage for the assignments, midterm and final exam will be:
25% Assignments, 35% Midterm, 40% Final.
There is no prescribed textbook for this course.
The union of the following two sources includes most of the topics covered in the
course, and a subset of their
union represents a good approximation to the course
syllabus.
- Algorithm Design, J. Kleinberg and É. Tardos. Addison-Wesley, 2005.
See Chapters 2 and 3 for basics on algorithm analysis and graphs.
Referred to as [KT] in Topics Covered.
- Approximation Algorithms, Vijay Vazirani. Springer-Verlag 2001.
Referred to as [V] in Topics Covered.
Portions from these texts relevant to the material covered in lecture, and possibly links
to some online sources
will be posted in the Topics Covered
section from time to time.
The topics in CO 453 Course Notes from Fall 2001 have a large disjoint portion from the
topics we will cover,
and our treatment of the common topics is different from the
treatment therein, so this is a less useful reference
than the name suggests.
The course notes are not available, but there are some very similar lecture notes (with
exercises)
of Joseph Cheriyan and R. Ravi on "Approximation Algorithms for Network Problems" available
here.
Some of the more relevant chapters from these notes are Chapter 1 [ps]
(graph basics, shortest paths), Chapter 5 [ps]
(MSTs: up to section 5.4), Chapter 8 [ps]
(primal-dual algorithm for 0-1 proper functions), and Chapter 2 [ps]
(set cover).
As mentioned earlier, not everything in these notes has been/will be covered, and not
everything that is
covered appears in the notes. The notes are also known to contain some
errors.
Some other useful books are:
- Introduction to Algorithms, T. Cormen, C. Leiserson, R. Rivest, and
C. Stein. McGraw-Hill 1990.
A standard reference book covering a wide variety of topics.
- Approximation Algorithms for NP-Hard Problems, D. Hochbaum, PWS Publishing
Company, 1997.
A more advanced-level reference book on approximation algorithms.
Tentative Course Outline
A large 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, then come and talk to me!
- Shortest paths: Dijkstra's algorithm
- Minimum Spanning Trees: the algorithms of Prim and Kruskal
- Minimum Cost Arborescences: Edmonds' algorithm
- Brief overview of the complexity classes P, NP; NP-Completeness and polynomial-time
reductions
- Approximation algorithms: the basic design paradigm; minimum Steiner trees
- Brief introduction to linear programming and duality, and its use in
approximation algorithm design
- The primal-dual schema: it's application to the Steiner tree problem, the generalized
Steiner forest problem,
the network connectivity problem with 0-1 proper functions
- The set cover problem: primal-dual algorithms, LP-rounding algorithms
- Uncapacitated facility location: the Jain-Vazirani primal-dual algorithm, the
Chudak-Shmoys LP rounding
algorithm
- The rent-or-buy network design problem
- Mechanism design for the minimum spanning/Steiner tree problem where edges are
strategic players
- Multicast cost sharing; cross-monotonic cost shares and group strategy-proof mechanisms
- The facility location game
- The network creation game