Randomized and Approximation Algorithms

Arizona State University, Fall 2008
CSE 591 (SLN 79117), in BYAC190 (Brickyard), TTh 10:30--11:45AM

Instructor: Goran Konjevod (email: my first name at asu.edu)
Office hours (Fall 2008): TTh 1:30-3:00 and by appointment
Office location: Brickyard 450.
TA: Melih Onus (email: first initial last name at asu.edu)
Office hours: MW 10:00--11:30, Brickyard 498.

Homework 1 due 9/9 in pdf. Homework 2 due 10/2 in pdf.

Notes: 8/26 (Quicksort, mincut);
8/28 (Basic inequalities, quickselect,coupon collector); 9/4 (Permutation routing);
Set Cover; Steiner Tree and TSP;

Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge
Vijay Vazirani, Approximation Algorithms, Springer

Overview (rough syllabus).

Books, papers and handouts:
Probabilistic inequalities (from A.Blum)
Bertsimas, Teo, Vohra: Dependent randomized rounding
Link to two surveys on random walks by Lovász
Doyle and Snell: Random walks and electric networks

Related pages: NP Optimization Compendium. Uri Feige on random walks.

Other randomized algorithms courses:
By Avrim Blum at CMU.
By David Karger at MIT.
By Anupam Gupta at CMU.

Metric methods by Anupam Gupta
Algorithmic aspects of game theory by Christos Papadimitriou
Random and high-dimensional algorithms by Jon Kleinberg
Structure of information networks by Jon Kleinberg