Winter 2018 - AAG - Approximation Algorithms

Administration

Instructor
Syamantak Das
B-512, New Acad Building
Email: syamantak@iiitd.ac.in

Lectures: Tuesday and Friday : 11:30am - 1pm in  CS 13
Office Hours: By appointment (send me an email)

Announcements

  • Take Home End Sem Exam, To be uploaded on Apr 28
  • Final Quiz on Fri, Apr 20
  • Short quiz on Fri, Mar 23
  • Short quiz on Tue, Jan 16

    • Course Description

    A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial time algorithms and proving bounds on their worst case performances.

    Prerequisites

    ADA, GA (or an equivalent graduate course in algorithms). Talk to the instructor if you have not taken one of the above courses but are comfortable with mathematical proofs and analytical reasoning and have taken an elementary course like discrete mathematics at any level.

    Grading

    The course grades will be determined based on:

    Assignment grading policy

    Each assignment will consist of 3-4 problems, each of which will carry 7 points. We shall follow Prof. Amit Chakrabarti's detailed grading policy. Please also refer to the "Working together and Honor Principles" on the same page.

    References

    Homework Assignments

    Final
    Assignment 2
    Assignment 3

    Course Plan

    Date Contents References Remarks
    Lecture 1 Tue Jan 2 Introduction and administrivia
    Why Approximation Algorithms?
    Problems: Maximum Matching, Load balancing on identical parallel machines     		1.1 from [WS]
    Section 1 from here
    Additional Reading: 2.3 from [WS]
    Lecture 2 Fri Jan 5 Metric TSP: MST heuristic, Christofides' Algorithm Section 2.4 from [WS]
    Lecture 3 Tue Jan 9 Greedy Algorithms
    Problems: Set Cover, Max-k coverage     		Old lecture notes
    Lecture 4 Fri Jan 12 Local Search
    Problems: Max-Cut, Max-Leaf spanning trees     		Lecture notes from R. Ravi's lectures in CMU
    Lecture 5 Tue Jan 16 Quiz 1, Local Search
    Problems: k-Median     		Sections 2.1 and 2.2 from this paper
    Lecture 6 Fri Jan 19 No lecture (Odyssey)
    Lecture 7 Tue Jan 23 Local Search ,PTAS
    Problems: k-Median, Knapsack     		Sections 3.1 from [WS] (Slightly different proof)
    Lecture 8 Tue Jan 26 No lecture (Institute Holiday)
    Lecture 9 Jan 30 PTAS
    Problems: P || C_max     		notes
    Lecture 10 Feb 2 LP Intro, Rounding
    Problems: Min Cost Bipartite Matching, R||C_max     		Section 11.1 from [WS]
    Lecture 11 Feb 6 LP Intro, Rounding
    R||C_max, uncapacitated facility location
    Lecture 12 Feb 9 Duality, Primal-Dual Algorithms
    Problems: Vertex Cover, Steiner Forest     		Chapter 12,22 from [VV]
    Lecture 13 Feb 13 Primal-Dual Algorithms
    Problems: Steiner Forest     		notes, Chapter 12,22 from [VV]
    Lecture 14 Feb 16 Primal-Dual Algorithms
    Problems: Prize Collecting Steiner Tree     		Chapter 14.1 from [WS]
    No lectures Feb 20-Mar 9 Mid Sem, Recess
    Instructor Travel    		 -
    Lecture 15 Mar 13 Randomized Approximation Algorithms
    Problems: Vertex cover, Rent-or-Buy Steiner Tree     		Anupam Gupta's lecture notes
    Lecture 16 Mar 16 Randomized Rounding
    Problems: Set Cover, Max Independent Set, PCST     		Deeparnab's lecture notes , pcst
    Lecture 17 Mar 20 Randomized Approximation Algorithms
    Problems: Max GAP, Low Congestion Routing     		Deeparnab's lecture notes
    Lecture 18 Mar 23 Quiz + Separation Oracles
    Problems: Low Congestion Routing
    Lecture 19 Mar 27 Rank Arguments, Iterative Rounding
    Problems: Min cost bipartite matching, Min GAP
    Lecture 20 Apr 3 Rank Arguments, Iterative Rounding
    Problems: Generalized Steiner Network     		notes, Section 11.3 from [WS]
    Lecture 21 Apr 6 Rank Arguments, Iterative Rounding
    Problems: Generalized Steiner Network     		Leftover from last lecture, Discussion on Group Steiner Tree
    Lecture 22 Apr 10 Rounding Semi-definite Programs
    Problems: Max-Cut     		Section 26.1-26.4 from [VV]