# CSCI2510: Approximation Algorithms (Spring 2015)

## Announcements

• 2015-02-25: Homework 5 is due at 5:00 pm on Friday, May 1. The problems are, from the textbook: 14.2, 14.4, and 15.6.
• 2015-02-25: Homework 4 is due at 9:59 am on Friday, April 17. The problems are, from the textbook: 8.2, 8.10, 8.11, 11.3, 11.5,
• Sixth problem: Assuming the structure theorem presented in class and found in Kolliopoulos and Rao, give a polynomial-time approximation scheme for k-median in the plane. This involves giving a dynamic program that takes advantage of the structure theorem. Though Kolliopoulos and Rao give a near-linear-time algorithm, yours need not run in near-linear time. It just needs to run in O(n^c) where c is independent of %epsilon. (The constant hidden by the big-O does depend on %epsilon.) The structure theorem asserts the existence of a portal-respecting solution whose cost is nearly optimum, so you need only show that your DP finds a best portal-respecting solution.
• 2015-02-25: Homework 3 is due at 9:59 on Wednesday, March 11. The Problems are:
• First problem: We studied an approximation algorithm for the bin-packing problem (Section 4.6). The algorithm used a linear program whose dual had an exponential number of constraints. Show that an separation oracle for the dual LP can be implemented by solving a knapsack problem. (The idea is that this reduction can be made approximate, that an approximation algorithm for the knapsack problem yields an approximate separation oracle, but you don't need to show this.)
• 7.2, 7.5, 7.6, 7.7(b)
• 2015-02-08: Class on Monday, February 9, is canceled due to snow.
• 2015-02-08: Homework 2 is due at the beginning of class on Monday, February 23. The problems are: 4.1, 4.3, 4.6, 4.7.
• 2015–01–26: Homework 1 is due at the beginning of class on Monday, February 3. The problems are 1.1, 1.2, 1.4, 1.6.

## Staff

• Professor: Philip Klein (email available at directory.brown.edu, CIT 511), office hours by appointment

• TA: David Meierfrankenfeld (`nfelddav@cs...`, CIT 453), office hours by appointment. Please do not hesitate to email me questions or to set up an appointment.

## Topics

The following chapters will be emphasized
Topics are subject to change.

• Ch 1: Introduction
• Ch 4: Deterministic Rounding
• Ch 7: Primal-Dual Method
• Ch 8: Cuts and Metrics
• Ch 11: More Deterministic Rounding
• Ch 12: Randomized Rounding
• Ch 14: More Primal-Dual Method
• Ch 15: More Cuts and Metrics
• Time permitting, sum-of-squares method

## Assignments

Problem sets will be assigned every 1 to 2 weeks. No exams will be given.

## Resources

Tutorial on sum-of-squares method

## 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).

## Collaboration Policy

In finding solutions to the problems in this class, you are allowed to collaborate with other students in the class. However, you should not retain any written (digitally or otherwise) record from your period of collaboration, and you should write up your solutions on your own, and list the names of those with whom you collaborated.

While the internet may be used to find other applications and analyses of techniques, do not look at solutions to the homework problems.

## Textbook

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