Fall 2001

- 4126 Upson.
- 255-0984
- eva@cs.cornell.edu

Time: WF 3:35-4:50P

Place: HO 362

Office hours: Thursday 2:30-3:30

Here is the style file for people scribing in Latex. Here is the tex file for the first lecture, so you see how to use these macros.

- 9/26 Minimum-cost flows (cycle canceling)
- 9/28 How to prove optimality and the primal dual algorithm
- 10/3 Making the primal-dual algorithm efficient using scaling
- 10/5 The preflow/push algorithm for min-cost flows
- 10/10 Linear programs, their dual and the general primal-dual algorithm
- 10/12 Primal-dual algorithm for finding minimum cost arborescence (directed tree)
- 10/17 The ellipsoid method for solving linear programs
- 10/19 Primal-dual approximation algorithm for the constrained forest problem.
- 10/24 Primal dual algorithm for the network design problem.
- 10/26: Primal-Dual Approximation Algorithms for Metric Facility Location
- Problem set 1 on primal-dual algorithms is due Friday, November 16th
- 10/31 Polynomial-time Approximation Schemes for Euclidean TSP
- 11/2 Min-cut based approximation algorithm for certain classification problem in vision
- 11/7 Access Network Design and the gathering problem
- 11/9 More on Network Design
- 11/14 Connectivity Network Design, Part I
- 11/16 Connectivity Network Design, Part II
- Problem set 2 is due
Wednesday, December 5th
- Problem 3 typo: the function f must be integral.

- 11/21-23 Thanksgiving break
- 11/28 Vickery auction and its variant for min cost spanning tree
- 11/30 Nash equilibrium for the first prize auction
- 12/5 Cost sharing for multicast
- The final Problem set 3
is due
Friday, December 14th.
- Problem 2(b) has been deleted! (as it asked you to prove a statement that is false).
- Poblem 1 typo: union of two EDGE-DISJOINT spanning trees.

- 12/7 Nash equilibrium

CS 684 is a new course designed to serve as an advanced follow-up to CS 681. The goal is to cover recent results and current problems, and illustrate a number of open directions of research in algorithms. The course pre-requisite is CS 681 or equivalent background in algorithms and discrete mathematics. The course is independent and essentially disjoint of CS 683 that was offered last spring.

The course focuses on current topics in the design of discrete algorithms. Topics include network flow algorithms, development of approximation algorithms for computationally intractable problems, role of game-theoretic concepts in algorithms, lattices, and the use of linear programming in combinatorial optimization. The course emphasizes algorithmic problems in a range of areas including networks, large datasets, and the design of heuristics.

(1) **Minimum cost flows.** CS 681 covers algorithms for the maximum
flow problem and many of its applications. Here we consider a more powerful
version of the problem, including costs, that has an even wider list of
applications. Minimum cost flows is has been a topic of extensive research.
Books such as Ahuja, Magnanti, and Orlin's book on Network Flows spends most of
its time on this topic. Here we will spend 1-2 weeks on this topic, which allows
us to cover the basic concepts such as pricing and equilibrium that allows one
to prove optimality of the flow, and the some of the best algorithms know for
the problem.

(2) **Brief introduction to linear programming and duality.** Linear programming is a powerful algorithmic
tool. Solving linear program can be useful in many algorithmic context. In
addition, linear programming duality provides an extremely useful tool for
algorithms design. Duality is a powerful proof technique;
it originates from the question,
"How do we prove that a solution of a system of linear
inequalities is optimal?" Such a "proof" can serve as an
extremely useful tool for algorithms design. We will see that the algorithm we
have seen so far, can be viewed as "primal-dual" methods, i.e.,
methods that make use of this technique to prove the constructed solution is
optimal (or close to optimal). In addition, a number of algorithms discussed in
CS 681 also can be viewed as primal-dual algorithms. One example that we
will review from CS 681 is the minimum-cost arborescence algorithm.

In addition of discussing duality, we will also cover briefly the simplest (though not the fastest) a polynomial time algorithm for this general problem.

(3) **Solving multicommodity flows.** Multicommodity flow is
an other widely used extension of basic flows, where different flows have their
own origin and destination. Multicommodity flows are widely used to model
routing application, such as routing traffic (messages, trucks, etc). They are
also the basis of many graph partitioning algorithms (that were covered in
CS 683). However, solving large multicommodity flow problems exactly is rather
slow. Here we will discuss a recent algorithmic approach for this problem that
yields close to optimal solutions very fast.

- N. Garg, J. Könemann: Faster and Simpler Algorithms for Multicommodity Flows and Other Fractional Packing Problems ; Proceedings of the 39th Annual IEEE Computer Society Conference on Foundations of Computer Science, 1998.

(4) **Approximation algorithms. **Most important problems are
NP-hard, and hence we cannot expect to be able to solve them exactly. The goal
of approximation algorithms is to provide provably close-to-optimal results.
Research on approximation algorithms has truly blossomed in the past decade. Amazing progress has occurred both in our
ability to design approximation algorithms and in proving limits to
approximability. In this course we will review many basic techniques for
approximation algorithms for various problems motivated by applications arising in vision, networking, and
clustering. Here is an approximate list of application areas and techniques that
we will cover.

- primal-dual algorithms for network design
and for facility location
- Kamal Jain, and Vijay V. Vazirani: Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems
- Michel Goemans and David Williamson: A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, 24:296-317, April 1995.
- D. Williamson, M.X. Goemans, M. Mihail and V. Vazirani, A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems, Combinatorica, 15, 435--454, 1995.
- M. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, E. Tardos, and D. Williamson: Improved approximation algorithms for network design problems. In the proceeding of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1994, pp. 223-232.

- greedy algorithms: The set cover problem, and its extensions. Network design problems.
- local search algorithms for a classification problem motivated by vision
- linear programming and rounding for a network design problem, and for classification
- approximation scheme for some problems in Euclidian metrics.

A superset of the papers this segment of the course will be based on:

- Adam Meyerson, Kamesh Munagala, and Serge Plotkin: Cost-Distance: Two Metric Network Design. Proceedings of 41st IEEE Symposium on Foundations of Computer Science, 2000.
- Fast Approximate Energy Minimization via Graph Cuts. Yuri Boykov, Olga Veksler, Ramin Zabih. In International Conference on Computer Vision (ICCV), 1999.
- J. Kleinberg and E. Tardos. Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Partitioning and Markov Random Fields, In the Proceedings of the 40th Annual IEEE Symposium on the Foundations of Computer Science, 1999.
- Kamal Jain: A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem to appear in Combinatorica.
- Sudipto Guha Adam Meyerson, Kamesh Munagala, Hierarchical Placement and Network Design Problems. Proceedings of 41st IEEE Symposium on Foundations of Computer Science, 2000.
- Sanjeev Arora. Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems. Journal of the ACM 45(5) 753-782, 1998.
- J.S.B. Mitchell (1996): Guillotine Subdivisions Approximate Polygonal Subdivisions:

Part II -- A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems, SIAM J. Computing .

(5) **Game theoretic concepts in algorithms design. **The emphasis
of this segment will be on techniques in the interface between algorithms and game
theory that can be used to address problems on networks. Topics include: Nash equilibrium and
other equilibrium concepts,

Social choice theory, Mechanism design, Multicast pricing, Worst-case equilibria and "the price of anarchy"

If
time permits.... (6) **Problems on lattices.**

Students taking the course will be required to take turns preparing lecture notes. In addition. there will be 4 problem sets, the last of which may be a take home final.