COMP5712¶
Course Name: Introduction to Combinatorial Optimization
Notes¶
| link | offering | format | author | remark |
|---|---|---|---|---|
| Homepage | 22-23Spring | LaTeX-generated PDF |
Review¶
Contents:
- Basic complexity classes
- Steiner Tree
- Metric Traveling Salesman
- Linear Programming, Duality
- Minimum Weighted Vertex Cover
- Set Cover
- Network flow, bipartite graphs, their LP formulations
- Steiner Forest
- Multiway Cut
- Max Cut
- Max SAT
Prerequisites: Basic linear algebra (vector product, matrix multiplication, used in the matrix formulation of LP, VP); Basic probability theory (Expectation); Basic algorithm (asymptotic notation, classical algorithms, e.g., MST, shortest path)