EECS 279: Approximation Algorithms

Fall 2015

Course Description

Optimization problems are prevalent in many disciplines, and computer science is no exception. Unfortunately, numerous optimization problems are computationally hard (eg. NP-hard), hence resist efficient algorithms. Approximation algorithms are polynomial time heuristics that aim to give a solution close to the optimum for all inputs. Although the focus is on guaranteeing the solution quality even in the worst scenario, the algorithmic ideas developed for approximation algorithms can be readily turned into useful heuristics in practice. The area of approximation algorithms has been a central topic in theoretical computer science for long, and now has a rich body of beautiful theories and results.

This course consists of two parts, ‘basic’ and ‘advanced’, which are concerned with roughly 2/3 and 1/3 of topics covered in the course, respectively. All students are expected to become familiar with the basic topics, and should be able to apply the acquired knowledge to their research. The advanced topics are about useful yet more sophisticated techniques that are needed to do serious research in the field of approximation algorithms.


Lectures: Tue, Thu, 10:00~11:15am in SSM 100.

Instructor: Sungjin Im, Office: SE2 214, email: sim3 at ucmerced

Office Hours: Thu, 11:30-12:30pm or by appointment

Prerequisite: CSE 100: Algorithm Design and Analysis, or an equivalent course.

Grading Policy: There will be six homeworks and a final exam. Each homework may be split into several smaller problem sets. All students are required to do the first four homeworks. Students must follow the homework guideline which can be found below. After that, students can choose to either do the last two homeworks or do a course project. Possible types of course projects include working on a theoretical problem, applying approximation algorithms to applications, or implementing approximation algorithms, etc. Projects must be approved by the instructor. More details can be found below.

Precisely, homework: 75% (6 * 12.5%), project: 25%, final: 25%.

This is a graduate course. Keep in mind that the ideal goal of the course project should be to advance your own research by applying approximation techniques.

Course Material

Recommended text books

·       The Design of Approximation Algorithms by David Williamson and David Shmoys, Cambridge University Press, 2011 (main).   

 * Online (but non-printable) version is available:

·       Approximation Algorithms by Vijay Vazirani, Springer-Verlag, 2004.

Other useful reference books

·       Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan

·       Combinatorial Optimization by Schrijver

·       Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.

·       Algorithm Design, Kleinberg and Tardos

Useful notes and slides from other places

·       Approximation Algorithms, Fall 2013, Spring 2011, Spring 2009 by Chandra Chekuri, UIUC.

·       Approximation Algorithms, Fall 2005 by Anupam Gupta and R. Ravi, CMU.

·       Algorithms lecture notes, old homeworks and exams by Jeff Erickson, UIUC.

·       Lecture notes and problems on algorithms by Sariel Har-Peled, UIUC.

·       Combinatorial Optimization, Spring 2010 by Chandra Chekuri, UIUC.

Topics to be covered (subject to change)

Approximation algorithm design techniques: Greedy approach, dynamic programming, randomization, local search, linear programming and rounding, semi-definite programming and rounding, and metric embedding.

Fundamental approximation problems:

·       Covering problems: vertex cover, knapsack cover, and set cover

·       Scheduling problems: single/multiple machine scheduling, precedence constraints, and generalized assignment

·       Packing problems: bin packing, knapsack, max coverage, and max independent set

·       Submodular optimization and its applications

·       Clustering: k-center, k-median, k-means, and facility location

·       Tour problems: metric TSP, asymmetric TSP, and orienteering

·       Network design problems: Steiner trees/forests, and survival network design

·       Cut problems: max cut, multiway cut, multicut, sparsest cut

·       Routing problems: multicommodity flow, congestion minimization, unsplittable flow


Intro to inapproximability: several well-known inapproximability results and approximation-preserving reduction

Schedule (subject to change)

  * CC: Chandra Chekuri lecture notes; WS: Williamson-Shmoys book; and V: Vazirani book.



Administrivia and Course Introduction

  Course Intro:

  - Section 1 in 2011 CC Lecture 1.

  - Chapter 1.1 in WS.

  Decision version of NP vs Optimization version of NP (NPO).

  - Section 2.1 in 2011 CC Lecture 2.

  - NP, P, NPC.

Course Intro (cont’) and Traveling Salesman Problem (TSP)

- Section 1 in 2011 CC Lecture 2.

- Chapter 2.4 in WS.

- Chapter 3.2 in V; tight examples are shown.

See NP, P, NPC. Weakly/strongly NP-hard

  - Quick overview

- lecture notes by Jeff Erickson

Lecture note by Chandra Chekuri on Minimum Spanning Tree

 Greedy Algorithms. Set Cover & Max Coverage

- Section 1 in 2011 CC Lecture 1.

- Section 1.6 in WS.

- Section 3.1 in V.

- Section 2 in 2011 CC Lecture 3.

Knapsack. PTAS/FPTAS.

- Section 1 in 2011 CC Lecture 6.

- Chapter 3 in WS.

- Chapter 8 in V.

Makespan on Identical Machines

- Section 1 in 2009 CC Lecture 5.

- Chapter 10 in V.

  - Chapter 3 in WS.

Bin Packing

- Section 1 in 2009 CC Lecture 5.

- Chapter 9 in V.

- Chapter 3.3 in WS.


- Chapter 5 in V.

- Chapter 2.2 in WS.

Scheduling jobs with precedence constraints on identical machines. Discussion on hw2A

  - Section 1 in 2009 CC Lecture 6


Multiway cut, k-cut

  - 2009 CC Lecture 7

 * See Jeff Erickson’s lecture note and Chandra Chekuri’s slides (1, 2, 3, 4) for max flow and min cut

 Introduction to LP and its applications to approximation algorithms

- Appendix A in WS.

- Chapter 1.3 in WS.

- Chapter 12 in V.

- 2009 CC Lecture 9,10

LP primal and dual: max flow and min cut, revisiting Set Cover.

  - Chapter 12 in V.

- 2009 CC Lecture 9,10

- Chapter 1 in WS.

- Chapter 13, 14, 15 in V.

Randomized Rounding, Chernoff Bounds

 - 2011 CC Lecture 9

 - Chapter 5.10, 5.11 in WS.


Facility Location

   - 2005 Anupam Gupta’s lecture note (10/31)

 - Chapter 4.5 in WS.

Scheduling Problems and Separation Oracle.

   - Chapter 4.1-4.3 in WS.

Introduction to Local Search: Weighted Max Cut

Local Search: k-Median

 - Section 2 in Lecture 6 of Anupam Gupta’s 2008 Advanced Approx. Algorithms.

 - Gupta and Tangwonsan’s analysis of local search for Facility Location and k-Median.

(Only the above topics will be tested in Final Exam)

Min-cost bipartite matching, Min makespan on unrelated machines, Generalized Assignment Problem (GAP).

 - Gupta and Ravi’s lecture note.

 - Chapter 11.1 in WS.

Group Steiner Tree.

 - Gupta and Ravi’s lecture note.


 - 2009 CC Lecture 18

Sparsest Cut

 - Gupta’s lecture note

Tree and L_1 Embeddings

 - Gupta’s lecture note

Online Algorithms

 - Lecture notes by Serge Plotkin

 - Who solved the Secretary Problem by T. Ferguson

 - A Primal-Dual Approach to Online Optimization Problems by Seffi Naor

 - Survey on Multiplicative weights update method by Arora, Hazan and Kale


Final Exam (3:00-6:00pm) in SSM 100


Project Deadline (11:59pm)


·       The ideal project would be the following.

- Find a problem in your area. Motivation and introduction are expected.

- Formalize the problem. You will need to decide what aspects to keep or discard. Balance is important: too many details will obscure algorithmic ideas and too few details will make the problem less realistic.

- Find connection to known problems. For some special cases, your problem may be already known. Summarize the previous work.

- Discuss the complexity of the problem. Is it NP-hard, or APX-hard?

- Give approximation algorithms if needed. This course is on approximation algorithms, so you are strongly encouraged to apply what you learned to your problem. 

- Try various methods: greedy, dynamic programming, linear programming and rounding, etc. Explain why they work or not. If you don’t know how to analyze, simply state that. If the general case is hard, you can try some special cases.

- Do some simple experiments if needed.

·       You are required to write a final report. I can hardly imagine a report of less than 5 pages that includes the intro, problem definition, attempted approaches, etc. But there exist really wonderful papers that are very short, so the length is not everything.

·       If you still haven’t chosen a project and have no idea, you can write a survey paper. For example,

-  Unconstrained Non-Monotone Submodular Function Maximization

§  A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization N. Buchbinder, M. Feldman, J. Naor, R. Schwartz. FOCS 2012

§  Maximizing Non-monotone Submodular Functions U. Fiege, M. Feldman, V. Mirronkni, J. Vondrak. FOCS 2012

- Potential Functions for Online Scheduling

§  A Tutorial on Amortized Local Competitiveness in Online Scheduling S. Im, B. Moseley, K. Pruhs. ACM SIGACT News (June 2011)

§  Scalably scheduling processes with arbitrary speedup curves J. Edmonds, K. Pruhs, SODA 2009

- Dual Fitting For Online Scheduling

§  Resource Augmentation for Weighted Flow-time explained by Dual Fitting S. Anand, N. Garg, A. Kumar. SODA 2012

§  SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors J. Kulkarni, S. Im, K. Munagala and K. Pruhs. FOCS 2014

§  Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling A. Gupta, R. Krishnaswamy, K. Pruhs. WAOA 2012

-  Dependent Randomized Rounding and Applications

§  Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee. A. Ageev and M. Sviridenko.
J. of Combinatorial Optimization 2004; preliminary version appeared as "Approximation algorithms for Maximum Coverage and Max Cut with given sizes of parts" in IPCO 1999.

§  Dependent Rounding and its Applications to Approximation Algorithms. R. Gandhi, S. Khuller, S. Parthasarathy, A. Srinivasan. J. of the ACM, 2006.

-  Solving Packing and Covering LPs Approximately

§  Randomized Rounding Without Solving the Linear Program. N. Young. SODA 1995.

§  Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems.. N. Garg and J. KonemannSIAM J. on Computing, 2007; preliminary version in FOCS 1998.

§  Multiplicative weights method: a meta-algorithm and its applications. S. Arora, E. Hazan, S. Kale.

§  Fast approximation algorithms for fractional packing and covering problem. S. Plotkin, D. Shmoys, E. TardosMath. of Operations Research, 1995; preliminary version in FOCS 1991.

Homework policy/guideline

·       You are strongly encouraged to type in their solutions in latex.

·       Solutions should be concise. Highlighting key ideas will be useful. Your goal is to convince me that you know the solutions.

·       You can discuss homeworks with others in groups of size up to 3. Each of you must submit your own solutions, and clearly note at the beginning of the first page the names of students you collaborated with.

·       One should not possess of a copy of all or part of the work done by someone else, in the form of an email, an email attachment file, a storage device, or a hard copy.

·       You can change their groups for each homework.

·       You can use materials found on the web or in books or papers. However, you must write the solutions in your own words and cite the sources clearly. 

·       There should be no student left alone unless the student wants to do so. If students do not follow this rule, the instructor has the right to change groups.

·       Deadline extension will be allowed up to one week only for the following reasons: illness or travel for academic reasons. You need to provide the proof such as a letter from doctor. Other reasons need to be approved by the instructor.

·       If you cheat on a homework, you will get zero point for the homework. If you cheat again, you will fail the course.