CSCI2510: Approximation Algorithms (Fall 2011)

Announcements

• 2011–10–21: Homework 5 is due in class Thursday, October 27 November 3 at the beginning of class. The problems are
  • 8.2
  • 8.3
  • 8.5
  • 8.6 except (c)
• 2011–10–13: Homework 4 is due in class Thursday, October 20 at the beginning of class. The problems are
  • 7.4 (modification of the Steiner forest approximation)
  • 7.6 (primal-dual for PC Steiner tree)
  • 7.8 (lemma for uncapacitated facility location)
• 2011–09–30: Homework 3 is due in class Thursday, October 6 at the beginning of class. The problems are
  • 6.1 (dual of the MAX CUT SDP)
  • 6.5 (Lovasz Theta Function)
  • 7.2 (multicut problem in trees)
  • 7.3 (local ratio technique for set cover and in general)
• 2011–09–22: Homework 2 is due in class Thursday, September 29 at the beginning of class. The problems are
  • 4.1 (SONET ring loading)
  • your choice of 5.1 (MAX k-CUT) or 5.3 (MAX DICUT)
  • 5.8 (variant of MAX SAT)
  • 6.2 (MAX 2SAT via SDP)
• 2011–09–15: Homework 1 is due in class Thursday, September 22 at the beginning of class. The problems are
  • 1.1 (partial cover)
  • 1.3 (metric ATSP)
  • 2.1 (k-suppliers)
  • 2.5 (Steiner tree)
  • 3.1 (greedy knapsack).
• 2011–09–09: the website is up.

Staff

• Professor: Philip Klein (klein@cs..., CIT 511), office hours by appointment

• TA: David Eisenstat (david@cs..., CIT 321), office hours by appointment. Please do not hesitate to email me questions or set up an appointment.

Calendar

November 8

• Minimum-congestion multicommodity flow

November 3

• The sparsest cut problem
• Embedding metrics into L1 with logarithmic distortion

November 1

• Euclidean TSP

October 27

• Buy at bulk
• Linear arrangements

October 25

• Approximating metrics by tree metrics

October 20

• Using multicut to minimize the number of unsatisfied clauses of a 2SAT formula
• Approximation algorithm for balanced cut

October 18

• Finished an LP-based approximation for the multiterminal cut problem
• An approximation algorithm for multicut

October 13

• Finished the k-medians algorithm
• Trivial 2-approximation for the multiterminal cut problem
• Started an LP-based approximation

October 11

• Finished a primal-dual 3-approximation for uncapacitated facility location
• Started an algorithm for k-medians based on uncapacitated facility location

October 6

• Finished a primal-dual 2-approximation for Steiner forest
• Started a primal-dual 3-approximation for uncapacitated facility location

October 4—class canceled

September 29

• Primal-dual algorithm for set cover
• Primal-dual algorithm for feedback vertex set in undirected graphs
• Primal-dual interpretation of Dijkstra’s algorithm
• started a primal-dual algorithm for Steiner forest

September 27

• Chernoff bounds (due originally to Bernstein)
• The congestion minimization problem
• Raghavan and Thompson’s randomized algorithm for congestion minimization
• Quadratic programs over +1/–1
• SDP approximation algorithm for same
• Correlation clustering
• SDP approximation for same
• Coloring a 3-colorable graph
• O(sqrt(n)) approximation
• SDP approximation

September 22

• MAX SAT: choosing the better of two solutions
• Review of PC Steiner tree
• Randomized 2.54-approximation for PC Steiner tree
• Semidefinite programs and positive semidefinite matrices
• The MAX CUT SDP
• Randomized rounding for the MAX CUT SDP

September 20

• Review of uncapacitated facility location and its primal and dual LPs
• Weak duality for the facility location LPs
• Deterministic 4-approximation for facility location
• Randomized 3-approximation for facility location
• MAX SAT and MAX CUT
• Algorithms for MAX SAT and MAX CUT based on the probabilistic method
• The MAX SAT LP
• Randomized rounding of the MAX SAT LP

September 15

• The Steiner tree problem
• An LP for the Steiner tree problem
• Formulating Steiner tree as a cut-cover problem
• The prize-collecting Steiner tree problem
• An LP formulation of PC Steiner tree
• A 3-approximation algorithm for PC Steiner tree (uses an exercise from Ch 7)
• The uncapacitated facility location problem
• Primal and dual LPs for uncapacitated facility location

September 13

• Primal-dual method
• The greedy algorithm for set cover
• Randomized rounding for set cover

September 8

• Motivation for approximation algorithms
• The set cover problem
• Linear programming relaxations
• Threshold-based rounding of the set cover LP
• The dual of the set cover LP
• Weak and strong duality
• Approximation algorithm for set cover based on solving the dual LP

Topics

• Ch 1: Introduction
• Ch 2: Greedy (skip)
• Ch 3: Rounding data and DP (no lectures)
  • knapsack (only in HW)
• Ch 4: Deterministic Rounding
  • Prize-collecting Steiner tree
  • Uncapacitated facility location
• Ch 5: Randomized rounding
  • MAX SAT and MAX CUT
  • Randomized Rounding
  • Choosing the better of two solutions
  • prize-collecting Steiner tree
  • uncapacitated facility location
  • Integer multicommodity flows
• Ch 6: randomized rounding of semidefinite programs
  • max cut
  • correlation clustering
  • coloring 3-colorable graphs
• Ch 7: primal-dual method
  • set cover
  • feedback vertex set
  • Steiner forest
  • …
  • uncapacitated facility location
  • k-median (using Lagrangean relaxation)
• Ch 8: Cuts and metrics
  • multiway cut problem
  • multicut
  • balanced cuts
  • approximation of metrics by tree metrics
  • buy-at-bulk network design
  • spreading metrics
• Ch 10: more rounding and
  • Euclidean TSP
  • Max independent set in planar graphs
• Ch 11: more deterministic rounding
  • iterated rounding
• Ch 12: more random rounding
  • uncapacitated facility location
  • single-source rent-or-buy?
  • Steiner tree 1.694?
  • exercise on ATSP
• Ch 14: more primal-dual method
  • prize-collecting Steiner tree
  • feedback vertex set
• Ch 15: more cuts and metrics
  • low-distortion embeddings and sparsest cut
  • oblivious routing, cut-tree packings
  • min bisection
  • uniform sparsest cut
• Neal Young’s view
• primal-dual method
  • include new method for PCST by Hajiah
• semidefinite programming/ Goemans and Williamson
• What I want to get to:
  • ARV
  • hierarchy of algorithms/semidefinite programming

Description

Approximation algorithms deal with NP-hard combinatorial optimization problems by efficiently constructing a suboptimal solution with some specified quality guarantees. We study techniques such as linear programming and semidefinite programming relaxations, and apply them to problems such as facility location, scheduling, bin packing, maximum satifiability or vertex cover. Prerequisite: one of the following: CSCI 1510, 1550, 1810, 1950J, 1950L, any graduate-level course on algorithms (including 2500A, 2500B, 2580).

Textbook

The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys.