Teaching
47-853 Special Topics on Combinatorial Optimization: Matroids and Submodular Optimization
About
This is a graduate-level course on matroids and submodular functions. We will cover the following topics: 1. submodular minimization (e.g., Lovász extension, principal partition), 2. submodular maximization (e.g., greedy, local search, continuous greedy, contention resolution scheme), and 3. matroids (e.g., matroid intersection, matroid union, packing and covering common bases/independent sets, matroid equitability).
Schedule
Location: TEP 5219, MW 9:00-10:50 am
Office hours: TEP 5201, Thu 2:00-3:00 pm
Note: Lecture notes are generated by AI from my handwritten notes. Please use them with discretion.
| Lecture | Topic | Content |
|---|---|---|
| Part I | Matroids and submodular minimization | |
| Lec 1 | Matroid Basics | Matroid axioms (independent set, basis, circuit, rank, closure); dual matroids; minors and operations. Readings: Oxley book (1965). |
| Lec 2 | Greedy and Matroid Intersection | Greedy algorithm; strong exchange properties; matroid intersection. Readings: Edmonds (1979); Lawler (1975). Optional: Weighted matroid intersection. Frank (1981); Brezovec, Cornuéjols, and Glover (1986). |
| Lec 3 | Matroid Union and Principal Partition | Spanning-tree packing; arboricity; matroid union; principal partition sequences of submodular functions. Readings: Tutte (1961); Nash-Williams (1961); Nash-Williams (1964); Kishi and Kajitani (1969); Narayanan (1991); Fujishige (2009). Optional: k-cuts via principal partition sequence. Barahona (2000); Ravi and Sinha (2007) |
| Lec 4 | Lovász Extension and Submodular Minimization | Matroid base polytope; polymatroids; submodular functions; Lovász extension; ellipsoid algorithm and submodular minimization; matroid intersection polytope; weight splitting. Readings: Edmonds (1970); Lovász (1983). Optional: Combinatorial submodular maximization. Queyranne (1998); Schrijver (2000); Iwata, Fleischer, and Fujishige (2001). |
| Part II | Submodular maximization | |
| Lec 5 | Greedy | $1/2$-approximation for monotone submodular maximization under a matroid constraint; $(1-1/e)$-approximation for monotone submodular maximization under a cardinality constraint; uniform-sampling $1/4$-approximation for unconstrained nonmonotone maximization. Readings: Nemhauser, Wolsey, and Fisher (1978); Cornuéjols, Fisher, and Nemhauser (1977); Feige, Mirrokni, and Vondrák (2011). Optional: Optimal double-greedy $1/2$-approximation for unconstrained nonmonotone maximization - Buchbinder et al. (2015). |
| 6 | Local search | Local-search $1/2$-approximation for monotone submodular maximization under a matroid constraint; geometric perspective of local search. Reading: Bruggmann and Zenklusen (2019). Optional: Iterated local-search $1/4$-approximation for nonmonotone submodular maximization under a matroid constraint - Lee et al. (2009). |
| 7 | Continuous greedy | Multilinear extension and other concave extensions; optimal continuous-greedy $(1-1/e)$-approximation for monotone maximization under a matroid constraint; measured continuous-greedy $1/e$-approximation for nonmonotone maximization under a matroid constraint. Readings: Călinescu et al. (2011); Feldman, Naor, and Schwartz (2011). |
| 8 | Rounding in the matroid (intersection) polytope | Pipage rounding and randomized swap rounding for matroids; randomized swap rounding for matroid intersection. Readings: Chekuri, Vondrák, and Zenklusen (2010); Chekuri, Vondrák, and Zenklusen (2011). |
| 9 | Contention resolution scheme (CRS) | FKG inequality; contention resolution for submodular maximization; simple $(b,1-b)$-balanced and optimal $(1,1-1/e)$-balanced schemes for the matroid polytope. Reading: Chekuri, Vondrák, and Zenklusen (2011). |
| 10 | Nonoblivious local search / Poisson process | Nonoblivious local search for monotone submodular maximization; Poisson process for monotone submodular maximization. Readings: Filmus and Ward (2014); Ganz Rozenman et al. (2026). Optional: Deterministic algorithm for monotone submodular maximization - Buchbinder and Feldman (2025); Poisson process for nonmonotone submodular maximization - Kulik et al. (2026). |
| Part III | Topics | |
| 11 | Packing and covering common bases / independent sets | Arborescence packing; hardness of packing common bases; matroid-intersection coloring. Readings: Edmonds (1973); Bérczi and Schwarcz (2021); Aharoni and Berger (2006); Arndt et al. (2026). Optional: Woodall’s conjecture on packing dijoins and approximation - Woodall (1978); Cornuéjols, Liu, and Ravi (2025). |
| 12 | Matroid equitability | Gabow’s conjecture; matroids are equitable. Readings: Gabow (1976); Akrami et al. (2026); Bérczi et al. (2026). Optional: Gabow’s conjecture and White’s conjecture on regular matroids - Bérczi, Mátravölgyi, and Schwarcz (2024). |
| 13 | Congruency-constrained matroids and submodular minimization | Delta-modular integer programming and congruency constraints; congruency-constrained submodular minimization. Readings: Artmann, Weismantel, and Zenklusen (2017); Nägele, Sudakov, and Zenklusen (2019). Optional: Congruency-constrained matroid bases - Liu and Xu (2024). |
Evaluation
You may choose one of the following two options.
| Option | Deliverables | Required discussion |
|---|---|---|
| Problem sets | HW1 (due: Sep 27 on Canvas) | Schedule one meeting with the instructor for each problem set and explain the solutions |
| Research report | Choose from an instructor-provided list of research questions, or suggest a topic subject to approval; write a 5-10 page report that summarizes the topic and suggests new research | Schedule one discussion with the instructor |
AI-use policy
- AI may be used to explore research topics.
- AI may not be used to solve homework problems.
- Every AI-assisted solution or result must be acknowledged.
- The final report and homework must be written by yourself.