CSc 80030: Approximation Algorithms

The Graduate Center, CUNY
Spring 2014
W 6:30pm-8:30pm
Room 3307

Course Description

CSc 80030: Approximation Algorithms: Survey of major techniques used in the design and analysis of approximation algorithms, i.e., algorithms providing guaranteed approximations for intractable optimization problems, including: greedy algorithms, local search, PTASs, LP rounding, randomized rounding, primal-dual, local ratio, factor-revealing LPs, SDP rounding, grid-shifting/treewidth PTASs. These general techniques will be introduced by studying their application to various canonical optimization problems such as:, set cover and max coverage, metric Steiner tree and TSP, multiway cut, knapsack, bin packing, vertex cover, scheduling problems, Steiner forest, Steiner network, facility location, multicommodity flow, MAX-SAT. Also a high-level overview of hardness of approximation.

Texts

  • Primary text: The Design of Approximation Algorithms
    by David P. Williamson and David B. Shmoys
    Hardcover: 516 pages
    Publisher: Cambridge University Press (April 26, 2011)
    Available at Amazon and in PDF.
  • Secondary text: Approximation Algorithms
    by Vijay V. Vazirani
    Hardcover: 380 pages
    Publisher: Springer (December 5, 2002) Available at Amazon and in PDF.

Grading

  • 2/3 - problem sets (~5)
  • 1/3 - project
    • The project can take the form of either an expository paper, a nontrivial implementation project, or (ideally) performing original research on a problem, which may be done in pairs.

    People

    Instructor: Prof. Matthew Johnson
    email: mpjohnson@gmail.com
    Office hours: By appointment. I'm typically at the Graduate Center MWF.

    Feedback

    I want the course to run smoothly, enjoyably and profitably. Feel free to let me know what you find good, interesting and fun about the course. Let me know sooner about the opposite.

    Homeworks

    • HW 3, problems 1 and 2 due before class on March 12; the rest: due before class on May 7
    • HW 2, due 7am, Tuesday 2/25/14
    • HW 1, due 6am, Monday 2/17/14

    (Tentative) Schedule

    1. (1/29) intro (approx, vertex over, set cover)

    2. (2/5) greedy (max coverage, scheduling, metric TSP/Steiner, k-center)
      reading: WS ch1 (just skimming the LP material) and ch2 (sec1-5), and V ch1 (all) and ch2 (sec1)

    3. (2/19) finish metric TSP and k-center; DP and data rounding (knapsack, min makespan sched, bin packing)
      reading: WS ch3; optional (and very concise) second take: V ch8,9,10

    4. (2/26) finish min makespan sched and bin packing

    5. (3/5) linear programming (duality, dual fitting (set cover), rounding (set cover))
      reading: V ch12 and ch13 (sec0,1 only) and WS ch1 (sec2,6) (see also WS app A if necessary)
      start deterministic LP-rounding (sched, facloc)
      reading: V14, WS ch1 (sec3,4) and ch4

    6. (3/12) deterministic LP-rounding (facloc, ellipsoid, bin packing)
      reading: W ch4 (sec3,5,6)

    7. (3/19) primal-dual (setcov, FVS, shortest path, Steiner forest)
      reading: V ch15, WS ch1 (sec4,5), & WS ch7.1; WS ch7.2; WS ch7 (sec3,4) & V ch22; W ch7.5; ?V ch25 & W ch7.6?

    8. (3/26) randomized LP-rounding (setcov, maxsat/maxcut, derand, facloc)
      reading: V ch16 and WS ch5 (sec1-6,8)

    9. (4/2) more primal-dual and local (facloc & k-median)
      reading: WS ch9 (sec0,1,4)

    10. (4/9) more greedy, dual-fitting, and factor-revealing LPs (facloc & k-median); more DP/PTASs (PTAS for Euclidean TSP)
      reading: "Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP" (sec1,2,3,9) & WS ch10 (sec1 - skim, because complicated)

    11. (4/23) more DP/PTASs (grid-shifting/treewidth-based PTASs for UDG/planar MIS, etc)
      reading: "Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI" (skim, because easy), and WS ch10 (sec2 - read closely, because complex and subtle); see also sec7 of Optimization Algorithms for Planar Graphs (ch14)

    12. (4/30) finish treewidth-based planar PTASs; local ratio (vertex cover, set cover, etc.); who knows, maybe more primal-dual (minimum knapsack)
      reading: "One for the Price of Two: A Unified Approach for Approximating Covering Problems", WS ch7 (sec5)

    13. (5/7) rounding SDPs (maxcut) and ??
      reading: V ch26, WS ch6 (sec1,2)

    14. (5/14) hardness of approx (gap-introducing and approx-preserving reductions, PCP, label cover, UGC)
      reading: WS ch16 & ch13 (first 2 pages of sec3)

    15. (5/21, finals week) project presentations

    mpjohnson@gmail.com