# CSCI2510: Approximation Algorithms (Spring 2018)

## Announcements

• Homework 5, due on May 4 at 11:00
• Worked through this paper on an approximation scheme for packing and covering LPs
• Homework 4: Problems 7.2, 8.11, 11.2, 15.5, due at beginning of class on April 11.
• Homework 3: Problems 6.2, 8.2, due at beginning of class on March 14.
• Homework 2: Problems 7.4, 7.6, 7.8, due at beginning of class on March 5.
• Homework 1 due at beginning of class on February 16.
• Syllabus
• The course calendar lists a guess as to topics per lecture

## Instructor

Professor: Philip Klein (email available at directory.brown.edu, CIT 511), office hours by 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.

Please don't use sources other than the textbook and lectures in connection with doing the homework problems.

## Textbook

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