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 | Handwritten notes |
| 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 minimization. Queyranne (1998); Schrijver (2000); Iwata, Fleischer, and Fujishige (2001). |
| Part II | Submodular maximization | Handwritten notes |
| Lec 5 | Greedy | Greedy for monotone submodular maximization under cardinality constraint; matroid constraint; uniform-sampling for unconstrained nonmonotone submodular maximization; multilinear extension. Readings: Nemhauser, Wolsey, and Fisher (1978); Cornuéjols, Fisher, and Nemhauser (1977); Feige, Mirrokni, and Vondrák (2011). |
| Lec 6 | Continuous greedy | Double greedy; continuous greedy; measured continuous greedy. Readings: Buchbinder et al. (2015); Călinescu et al. (2011); Feldman, Naor, and Schwartz (2011). |
| Lec 7 | Local search | Local search for monotone submodular maximization under matroid constraint; matching constraint; polyhedral view of local search. Reading: Bruggmann and Zenklusen (2019). Optional: monotone submodular maximization under k matroid constraints Lee et al. (2009); Singer and Thiery (2026). |
| Guest Lec 8 by R. Ravi | Rounding in the matroid (intersection) polytope | Pipage rounding; randomized swap rounding; negative correlation and concentration. Readings: Chekuri, Vondrák, and Zenklusen (2010). Optional: Randomized swap rounding for matroid intersection Chekuri, Vondrák, and Zenklusen (2011). |
| Guest Lec 9 by Jai Moondra | Contention resolution scheme (CRS) | FKG inequality; CRS for submodular maximization; combining schemes; optimal CRS for the matroid polytope. Reading: Chekuri, Vondrák, and Zenklusen (2011). |
| Lec 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 | Handwritten notes |
| Lec 11 | Packing common bases | Strongly base-orderable (SBO) matroids; packing common bases of SBO matroids; arborescence packing; submodular flows; dijoins and dicuts; Lucchesi–Younger theorem; Woodall’s conjecture. Readings: Davies and McDiarmid (1976); Edmonds (1973); Lucchesi and Younger (1978); Edmonds and Giles (1977). Optional: Approximately packing dijoins Woodall (1978); Cornuéjols, Liu, and Ravi (2025); hardness of packing common bases Bérczi and Schwarcz (2021); Hörsch et al. (2024). |
| Guest Lec 12 by Stephen Arndt | Matroid intersection coloring | Aharoni-Berger conjecture; Rota’s conjecture; approximation algorithms. Readings: Aharoni and Berger (2006); Arndt et al. (2026). Optional: Asymptotic Rota Montgomery and Sauermann (2025). |
| 13 | Matroid equitability | Gabow’s conjecture; matroids are equitable. Readings: Gabow (1976); Akrami et al. (2026); Bérczi et al. (2026). Optional: Gabow’s conjecture on regular matroids Bérczi, Mátravölgyi, and Schwarcz (2024); Oki and Schwarcz (2026). |
Evaluation
You may choose one of the following two options.
| Option | Deliverables | Required discussion |
|---|---|---|
| Problem sets | HW1 (due: Sep 27 on Canvas) HW2 (due: Oct 18 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 (due: Oct 18 on Canvas) | Schedule a 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.