CS G399: Topics in Theories of Computer Science

Algorithmic Power Tools I

Fall 2007

Mailing list

Please make sure you are on the class mailing list; if not, please contact the instructor Ravi Sundaram.

Tentative Calendar
 
 

 Week 

Topic

Handouts

Scribe

Suggested Reading

 

 

 

 

 

Jan 8, 11

Introduction to Game Theory. Nash Equilibrium.

Complete proof via Sprener’s Lemma, Brouwer’s and

Kakutani’s Fixed Point Theorems. Applications.

Nash

Zhifeng Sun

Vazirani, Ch 1, 2

Jan 15, 18

Congestion Games and Potential Games. Equivalence of

Congestion Games with Exact Potential Games.

General Potential Games. Examples.

Games

Alok Bhide

Yishay Mansour’s

lecture notes

Jan 22, 25

NP-completeness – overview. PLS-completeness.

MINCIRCUIT/FLIP is PLS-complete. PLS-completeness

of finding Nash Equilibria in Congestion Games.

PLS-complete

Evangelia Molyva

Scan of book to come

Jan 29

Ladner’s Theorem

Ladner

San Tan

Jonathan Katz’

Lecture notes

Oct 2, 5

Wrap up local search analysis
The primal-dual schema

KMedian
PrimalDualIntro

Jian Wen

Goemans-Williamson
Vazirani, Ch 15

Oct 9, 12

Case study: Network design
Goemans-Williamson algorithm for Steiner forest

SteinerForest
SteinerNetworkIntro

Laura Poplawski

Goemans-Williamson
Jain
Vazirani, Ch 22, 23
Korte-Vygen, Ch 20

Oct 16, 19

Case study: Network design, contd
Jain's algorithm for Generalized Steiner Network

SteinerNetwork1
SteinerNetwork2

Hooman Javaheri

Jain
Vazirani, Ch 22, 23
Korte-Vygen, Ch 20

Oct 23, 26

Case study: Multicommodity Flow & Sparsest cut
Leighton-Rao algorithm

UniformMCF1
UniformMCF2

Zhifeng Sun

Leighton-Rao
Vazirani, Ch 21

Oct 30, Nov 2

Primal-dual approximation scheme for multicommodity flow
SEMI-DEFINITE PROGRAMMING (SDP):
Shannon's theory of information
Shannon capacity of a graph

Problem Set 2
MCFApprox

InformationTheory

Emrah Bayraktaroglu

Young
Garg-Konemann
Korte-Vygen, Sec 19.2
Shannon

Nov 6, 9

Semi-definite programs
Case study: Shannon capacity of the Pentagon

Pentagon
SDP

Jingjing Duan

Lovasz notes
Goemans-Williamson

Nov 13, 16

Rounding SDPs
Case study: Max-Cut
Case study: Sparsest cut

 

Abhishek Chaubey

 

Nov 20

Case study: Sparsest cut
Metric Embeddings and applications

 

Tao Jin

 

Nov 27, 30

Case study: Sparsest cut, contd
Arora-Rao-Vazirani algorithm

Sample Solution to PS1
Problem Set 3

Shahzad Rajput
Stefan Savev

 

Dec 4, 7

PROBABILISTIC TECHNIQUES
Random sampling
Case study: Fingerprinting
Random walks and Markov chains
Case study: HITS algorithm and Google's Pagerank

 

Max Bandazian
Xin Dong

 

Dec 11, 14

Student presentations

 

 

 


 For the scribe notes, here are the latex 2e macros files (and the latex source for the first lecture as a sample)


References

Books

Vijay Vazirani, Approximation Algorithms, Springer-Verlag, Berlin, 2001.   

Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995.

Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2006

Bernard Korte and Jens Vygen, Combinatorial Optimization: Theory and Algorithms, 3rd edition, Springer, 2005.

Facility Location

J.-H.  Lin and J. Vitter, Approximation algorithms for geometric median problems, IPL 1992

D. Shmoys, E. Tardos, and K. Aardal,  Approximation algorithms for facility location problems, STOC 1997

R. Mettu and C.G. Plaxton, The Online Median Problem, SICOMP 2003

K. Jain and V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, JACM 2001

V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit, Local Search Heuristics for k-Median and Facility Location Problems, SICOMP 2004

A. Archer, R. Rajagopalan and D. B. Shmoys, Lagrangian relaxation for the k-median problem: new insights and continuity properties, ESA 2003

Network Design

M. Goemans and G. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, 24, 296--317, 1995.

M.X. Goemans and D.P. Williamson, The Primal-Dual Method for Approximation Algorithms and its Application to Network Design Problems, in Approximation Algorithms, D. Hochbaum, Ed., 1997.

K. Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica 21(1): 39-60 (2001)

Multicommodity Flow and Sparsest Cut

T. Leighton and S. Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, JACM 1999

N. Young, Randomized rounding without solving the linear program, SODA 1995

N. Garg and J. Könemann, Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems, FOCS 1998

Information Theory and Shannon capacity

C. E. Shannon, ``A mathematical theory of communication,'' Bell System Technical Journal, vol. 27, pp. 379-423 and 623-656, July and October, 1948.
 
C. E. Shannon, ``The Zero Error Capacity of a Noisy Channel,'' Institute of Radio Engineers, Transactions on Information Theory, Vol. IT-2 (September, 1956), pp. S8-S19. Reprinted in D. Slepian, editor, Key Papers in the Development of Information Theory, IEEE Press, NY, 1974. Included in Part A.

S. Arora, S. Rao, and U. Vazirani, Expander Flows, Geometric Embeddings and Graph Partitioning, STOC 2004

Semi-Definite Programming

L. Lovász, Semidefinite programs and combinatorial optimization (Lecture notes) (1995) 

M. Goemans and D. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, JACM 1995

S. Arora, S. Rao, and U. Vazirani, Expander Flows, Geometric Embeddings and Graph Partitioning, STOC 2004

Geometric Techniques

Probabilistic Techniques