Time: Monday and Wednesday 7:30 pm - 8:50 pm
Place: Science & Engineering Resource Center (SEC), Room 208
Instructor: Peng Zhang (Email: pz149@cs.rutgers.edu)
Office Hours: TBA Office: Hill Center 444
Course description
A combinatorial optimization problem is a problem of maximizing a real-valued objective function on a finite set of feasible solutions usually represented by 2^E — the set of all subsets of a finite ground set E. Examples include minimum spanning trees, maximum matchings, and network flows and cuts. Combinatorial optimization is closely related to operations research, algorithms, and computational complexity theory. It has numerous applications in artificial intelligence, machine learning, auction theory, applied mathematics, and theoretical computer science. Throughout this course, we will develop efficient algorithms that are provably better than enumerating all feasible solutions.
Prerequisites
Familiarity with discrete structures, probability theory, and design and analysis of algorithms, e.g., as in 01:198:205, 01:198:206, 01:198:344 or 16:198:512 or 16:198:513, or an equivalent background. Knowledge of LP duality is useful but not a prerequisite.
Tentative Topics
Polytopes and linear programming: convex sets, linear-programming duality, polytopes, totally unimodular matrices, graphs
Matroids: example of matroids, the greedy algorithm, rank properties, duality, the matroid polytope
Matroid intersection: applications, ordinality matroid-intersection algorithm, maximum-weight matroid-intersection algorithm, the matroid-intersection polytope
Matching: augmenting paths and matroids, the matching polytope, duality, maximum matching algorithm
Flows and cuts: source-sink flows and cuts, max-flow algorithms
Submodular function optimization
References
A First Course in Combinatorial Optimization, by John Lee
A Course in Combinatorial Optimization, by Alexander Schrijver
Grading
Problem sets (45%): 3 problem sets
Project (30%): presentation (last week in class)
Scribe notes (25%)
Schedule
9/6: Intro of combinatorial optimization, definitions of convex sets, polytope, Fourier-Moztkin elimination for linear equality systems (Ref: Lee's book Chapter 0.1)
9/11: Weyl's theorem, the theorem of the alternative for linear inequalities (Farkas lemma) (Ref: Lee's book Chapter 0.1)
9/13: Linear program duality (Ref: Lee's book Chapter 0.2)
9/18: Complementary-slackness (Ref: Lee's book Chapter 0.2)
9/20: Polytopes, faces (Ref: Lee's book Chapter 0.5)
9/25: Polytopes, Minkowski's theorem (Ref: Lee's book Chapter 0.5)
9/27: Matroids: definition and examples (Ref: Lee's book Chapter 1.1)
10/2: The greedy algorithm (Ref: Lee's book Chapter 1.4)
10/4: Rank properties (Ref: Lee's book Chapter 1.5)
10/9: Matroid duality (Ref: Lee's book Chapter 1.6)
10/11: Matroid polytope (Ref: Lee's book Chapter 1.7)
10/16: Applications of matroid intersection (Ref: Lee's book Chapter 3.1)
10/18: An efficient cardinality matroid-intersection algorithm (Ref: Lee's book Chapter 3.2)
10/23: Proofs for the cardinality matroid-intersection algorithm (Ref: Lee's book Chapter 3.2)
10/25: Maximum-weight matroid-intersection algorithm (Ref: Lee's book Chapter 3.3); matching, augmenting paths and matroids (Ref: Lee's book Chapter 4.1)
10/30: Bipartite matching polytope (Ref: Lee's book Chapter 0.8)
11/1: Konig's theorem and Hall's theorem for bipartite matching (Ref: Lee's book Chapter 0.8)
11/6: General graph matching polytope and duality (Ref: Lee's book Chapter 4.2 and 4.3)
11/8: Algorithm for maximum-cardinality matching (Ref: Lee's book Chapter 4.3)
11/13: Source-sink flows and cuts (Ref: Lee's book Chapter 5.1)
11/15: Max-flow algorithm (Ref: Lee's book Chapter 5.2) reduce finding a feasible flow to max-flow with flow lower bounds 0
11/27: Runtime of the max-flow algorithm (Ref: Lee's book Chapter 5.2)
11/29: Optimizing submodular functions (Ref: Vondrak's lecture notes)
12/04: The greedy algorithm for submodular maximization, continuous extension for submodular minimization (Ref: Vondrak's lecture notes 16 and 17)
12/06: Submodular maximization application in social network (Ref: Maximizing the Spread of Influence through a Social Network, by Kempe, Kleinberg, and Tardos)
12/11 and 12/13: Presentation