_ **Times:** Tue/Thu 3:00PM - 4:20PM

_ **Location:** Building 380, 380X

_ **Instructor:** Amin Saberi
(saberi at stanford),
Office hours: Thursday 4:30-6:00 pm

_
**Algorithm Design** by
Kleinberg and Tardos, 2005

_
**Discrete
Mathematics** by Lovasz, Pelikan and Vesztergombi, 2003

_
**Combinatorial
Optimization**, by Cook, Cunningham, Pulleyblank
and Schrijver, 1997

**Topics:** linear
program duality and LP solvers; integer programming; combinatorial optimization
problems on networks including minimum spanning trees, shortest paths, and
network flows; matching and assignment problems; dynamic programming; linear
approximations to convex programs; NP-completeness.

**Applications:** topics
will be illustrated with applications from operations management,
bioinformatics, computer systems, and electronic commerce.

_ **Homework:** 4 homework assignments of 10% each.

_
**Homework
dates:** Jan 19-31, Jan 31-Feb 14, Feb 14-Feb 28, Feb 28-Mar 14.

_
**Midterm:** in
class and closed book on Feb 14, and 30% of the grade.

_
**Final:** 35%. (if you get more than 100, you will get an A+ in this class).

_
Lecture 1: Basic
Graph Theory Concepts, Trees, Cayley's Theorem. See the **notes **as well as **Graph Theory slides**

_
Lecture 2: Eulerian
Circuits and DNA sequencing. See the ** notes**. Also check
out

_
Lecture 3: Minimum
Spanning Trees. See the __notes. __

_
Lecture 4: Network
flows, maximum-flow minimum-cut theorem. See the ** notes** as well as
the

_
Lectures 5 &
6: Applications of networks flows. See the ** notes** as well as
the

_
Lecture 7: ** Linear programs ** (A quick review). See also

_
Lecture
8: **Minimum cost flows.** See
also ** chapter 5** of BVR.

_
Lectures 9 & 10: **Approximation algorithms I**.
See also the **additional material** on NP-Completeness.

_
Lecture 11: The **stable marriage problem**.
See also **this** on practical
applications.

_
Lectures 12 & 13: **Approximation algorithms II**.
See also chapter 26 of **VaziraniÕs book** on maximum cut
and semidefinite programming.

_
Lecture 13 & 14: SpernerÕs
lemma and applications: BrouwerÕs fixed point
theorem, fair allocation, and rental harmony. See SuÕs **excellent exposition**. You can also look
at this **note** with a more
mathematical treatment for your information.

_
Lecture 15: mechanism design and sponsored auctions. See
these **slides.**

_
** Homework 1** (due Jan 31

_
** Homework 2** (due Feb 14

_
** Homework 3** (due Feb 28

_
** Homework 4** (due Mar 14

_ __2016 midterm and solutions.__

- Motivation for the course: (1
week)
- several examples
- LP vs IP
- np-hardness
- approximation algorithms
- Basic graph theory (3 weeks)
- Graphs, Trees, Cayley's Theorem
- Depth First Search, Breadth First
Search
- Minimum Spanning Trees
- Eulerian graphs, Hamiltonian
graphs
- Running time, Asymptotics
(1 week)
- Refresh LP and duality -- simplex
(1 week)
- Shortest path, matching, flow,
min-cost flow, several applications (4 weeks)
- NP-completeness (2 weeks)
- Approximation algorithms (4 weeks)