Times | Tue/Thu 3:00PM - 4:20PM | ||
---|---|---|---|

Location | McCullough 112 | ||

Instructor | Amin Saberi (saberi at stanford) | Office Hours | Thursday 4:30-6:00 pm |

Course Assistants | Nolan Skochdopole (naskoch at stanford) | Wednesday 2:00-4:00 pm (basement of Huang) |

## Recommended Texts

- Algorithm Design by Kleinberg and Tardos, 2005
- Discrete Mathematics by Lovasz, Pelikan and Vesztergombi [LPV] (available here for Stanford IPs)
- Combinatorial Optimization, by Korte and Vygen, Theory and Algorithms, 2002
- Combinatorial Optimization, by Cook, Cunningham, Pulleyblank and Schrijver, 1997

## Class Discription

Combinatorial and mathematical programming (integer and non-linear) techniques for optimization.

**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.

## Course Load and Grading

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

**Midterm:**in class, close-book, and 30%

**Final:**35%.

(if you get more than 100, you will get an A+ in this class).

## Tentative Outline

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