Advanced Algorithms
I plan to cover some advanced techniques in algorithm design, for example, use of linear programs, randomization etc.
Students taking this course should have done one course on programming,
and one on design and analysis of algorithms.
I also expect familiarity with basic concepts in probability.
Top
There is no single textbook for the course.
We will initially cover material from the following books:
- [VV] Approximation algorithms by Vijay Vazirani
- [WS] The design of approximation algorithms by Williamson, Shmoys
I will post other references as and when I cover topics outside these books.
Top
There will be two quizzes, a mid-semester exam, and an end-semester exam.
Top
You are not supposed to discuss the assignments with anyone or refer to any
source on the internet. Students found copying assignments from each other
will get a fail grade. If you are stuck while solving the assignment, you
are welcome to discuss with me. I will be glad to give hints so that you can
proceed. Assignments submitted after the due date will not be accepted.
Assignment 1 due on September 3.
Assignment 2 due on October 3.
Assignment 3 due on November 26
Top
Module 1: Approximation Algorithms
- August 7: Introduction to approximation algorithms, 2-approximation
for vertex cover, greedy algorithm for set cover [VV]
- August 9: Analysis of greedy set cover: O(log n) approximation,
inapproximability of the traveling salesman problem [VV,WS]
- August 14: 2-approximation for metric TSP, 3/2-approximation by
Christofide's algorithm (Technique: Use of two lower bounds)[VV]
- August 16: Local search: 2-approximation to List scheduling (minimum makespan), list scheduling using LPT rule: 4/3 approximation [WS]
- August 21: List scheduling by LPT rule continued, definition of
PTAS, PTAS for list scheduling with constant number of machines[WS]
- August 23: PTAS for list scheduling by rounding[WS]
- August 28: Bin-packing: Hardness, inapproximability, first-fit
algorithm and analysis, APTAS
- September 4: Introduction to LP, deterministic rounding for
weighted vertex cover, introduction to duality
- September 6: Strong duality and complementary
slackness condition (without proof), primal-dual algorithm for
weighted vertex cover (Ref)
- September 11: Steiner tree 2-approximation, LP formulation for
prize-collecting Steiner tree (Ref: [VV] for 2-approximation, [WS] for LP formulation)
- September 13: Prize-collecting Steiner tree: 3-approximation by
deterministic rounding of LP (Ref: [WS])
- September 18: Prize-collecting Steiner tree continued: solving the
LP by ellipsoid method, polynomial-time separation oracle for
the prize-collecting Steiner tree LP (Ref: [WS])
- September 20: Steiner tree primal-dual algorithm (Ref: [WS])
Module 2: Randomized Algorithms
- October 4: Introduction to randomized algorithms, randomized
2-approximation to weighted MAX-SAT, derandomization using
conditional expectation (Ref: [WS])
- October 9: Improving the approximation for weighted MAX-SAT using
biased coins, further improvement using randomized LP rounding ([WS])
- October 11: Improved approximation for prize-collecting Steiner
tree using randomization [WS], Karger's min-cut algorithm (Ref)
- October 16: Faster min-cut algorithm by Karger and Stein (Ref as before, and this)
- October 18: Network reliability (Ref)
- October 23: Network reliability continued
- October 25: Enumerating small cuts: Coupon-collector paradigm,
FPRAS for DNF counting (Ref)
- October 30: Polynomial identity testing and its application to
bipartite matchings (Refand this)
November 6: Problem Discussion: k-center 2-approximation, matchings
in general graphs using PIT
- November 8: Isolation lemma, bipartite matchings in RNC
- November 13: Lovász Local Lemma: Non-constructive proof and
application to k-CNF SAT (Ref)
- November 15: Algorithmic Lovász Local Lemma: randomized k-SAT (Ref: As above)
- November 20: Online bipartite matching (Original paper and this paper for the proof
presented in class)
- November 22: Online bipartite matching continued