Approximation and Network Algorithms

Computer Science 684
Fall 2001


Éva Tardos

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.

What we covered so far


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.

Tentative Course Outline 

(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.

(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.

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

(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.  

Course Work

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.