This image is from the textbook "The Approximation Algorithms" by V. Vazirani, 2004.










Announcements.

  • Office hour: 2pm - 3pm every Friday in EC445.


Topics

Slides & Lecture Notes

W1 - 9/17

Intro, Basic Concepts,
FPTAS for the Knapsack Problem,
Existence of FPTAS

Note #1 (updated)

W2 - 9/24

Asymptotic PTAS for the Bin Packing Problem

Homework #1 is available. Due: 10/8

W3 - 10/1

Greedy towards Cost-Efficiency :
O(log n)-approximation for Set Cover

3-Set Cover.pdf
(p.27, p.37 updated)

W4 - 10/8

The k-Center Problem

Homework #2 is available. Due: 10/29

W5 - 10/15

Introduction to LP-based Methods,
Simple rounding scheme

W6 - 10/22

Extreme point structure of LPs,
Half-integrality of vertex cover,
Unrelated machine scheduling

W7 - 10/29

Introduction to LP duality,
Simple dual-fitting scheme

7-LP Duality.pdf
(tentative, to be updated)

W8 - 11/5

The strong duality of LPs,

Jamboard #1
Jamboard #2

Note #8
(to be updated)

W9 - 11/12

Complementary Slackness Theorem,

The facility location problem (I) : clustering & rounding

Jamboard #1
Jamboard #2
Jamboard #3

W10 - 11/19

The facility location problem (II) : dual-fitting

Homework #3 is available. Due: 12/31

W14 - 12/17

Semidefinite programming,
The max-cut problem

About W14 - W18 , Homework #4 is available. Due: 1/21

The multiway cut problem

1/14

** Final Exam ** 1/14 (Fri) 14:00 - 17:00 ED102

The facility location problem (III): the factor-revealing techniques

Primal-Dual Schema, Reinterpretation of (a few) combinatorial approaches
Total unimodularity

Iterative rounding,
The Steiner network problem

Capacitated Cover,
Metric TSP & Euclidean TSP