E0 326 · Topics in Combinatorial Optimization

Course overview

This course develops foundational ideas and algorithmic techniques for efficiently solving combinatorial optimization problems. The main emphasis is on packing and covering problems and on discrete fair division, while continually connecting recent advances with classical results.

Students will encounter linear programming, discrepancy, competitive and probabilistic analysis, graphs and hypergraphs, matroids, and topological methods. The course is designed for students who want both a rigorous toolkit and a view of current research directions.

Approximation Algorithms Online Algorithms Geometric Packing Beyond Worst-Case Probabilistic Analysis Hypergraph Matching Matroids Sperner's Lemma Graph Decompositions

Lectures

Module00

Background

A compact refresher on approximation guarantees, linear programming, probability, rounding, and primal–dual methods used throughout the course.

Approximation basics Linear programming Probability · rounding

Resources

Approximation-algorithms background materials are drawn from the Approximation Algorithms (2022) course page.

Background resources

Notes Probability refresher
Video Definitions of approximation ratio, PTAS, and asymptotic approximation
Video Introduction to Linear Programming
Video LP Duality
Video Algorithms for LP
Video Extreme Point Solutions
Video Deterministic Rounding
Video Randomized Rounding
Video Primal–Dual Schema
Video Dual Fitting

Module01

Greedy Algorithms and Weight Functions

Weight-function techniques for analysing classical bin-packing heuristics, with detailed studies of Next Fit, First Fit, and First Fit Decreasing.

Greedy algorithms Weight functions NF · FF · FFD

Resources

Papers

Paper	Authors	Year
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms	D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, R. L. Graham	1974
The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9 OPT(I) + 6/9	György Dósa	2007

Additional resources

Video Greedy Algorithms — Part 1
Video Greedy Algorithms — Part 2
Demo Interactive greedy bin-packing comparison lab

Module02

Competitive Analysis and Lower Bounds

Competitive analysis for online bin packing, Harmonic rounding and size classes, and Yao’s lower-bound construction.

Competitive analysis Harmonic rounding Yao lower bound

Resources

Papers

Paper	Authors	Year
New Algorithms for Bin Packing	Andrew Chi-Chih Yao	1980
A Simple On-Line Bin-Packing Algorithm	C. C. Lee, D. T. Lee	1985
On the Online Bin Packing Problem	Steven S. Seiden	2002

Module03

Linear Grouping and APTAS

Linear grouping and rounding for one-dimensional bin packing, centred on the asymptotic PTAS of Fernandez de la Vega and Lueker.

Linear grouping APTAS Size rounding

Resources

Papers

Paper	Authors	Year
Bin Packing Can Be Solved within 1 + ε in Linear Time	W. Fernandez de la Vega, George S. Lueker	1981

Additional resources

Book Williamson–Shmoys, The Design of Approximation Algorithms — Chapter 3.3 — Bin-packing APTAS via linear grouping; this is the main textbook reference for this part.

Module04

Separation Oracle and Iterative Rounding

The configuration linear program, optimization–separation, and the Karmarkar–Karp iterative rounding framework for bin packing.

Separation oracle Configuration LP Karmarkar–Karp

Resources

Papers

Paper	Authors	Year
A Linear Programming Approach to the Cutting-Stock Problem	P. C. Gilmore, R. E. Gomory	1961
Bin Packing Can Be Solved within 1 + ε in Linear Time	W. Fernandez de la Vega, George S. Lueker	1981
An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem	Narendra Karmarkar, Richard M. Karp	1982
The Ellipsoid Method and Its Consequences in Combinatorial Optimization	Martin Grötschel, László Lovász, Alexander Schrijver	1981

Additional resources

Book Williamson–Shmoys — Chapter 4.6 — Harmonic-grouping approach yielding OPT + O(log² OPT).
Book Lau–Ravi–Singh, Iterative Methods in Combinatorial Optimization — Chapter 13.5 — Geometric grouping closer to the original Karmarkar–Karp approach; also discusses solving the configuration LP via the ellipsoid method and repeatedly exploits structure of extreme-point solutions.
Video Ryan O’Donnell — Ellipsoid Method
Appendix Multiplicative-weight approach to solving the configuration LP — Appendix B — An alternative based on Plotkin–Shmoys–Tardos multiplicative-weight updates.
Book Grötschel–Lovász–Schrijver — Geometric Algorithms and Combinatorial Optimization — Detailed reference for the ellipsoid method.

Module05

Discrepancy-Based Rounding

Constructive discrepancy minimization via the Lovett–Meka edge-walk and its use in the Hoberg–Rothvoss bin-packing algorithm.

Lovett–Meka Partial coloring Hoberg–Rothvoss

Resources

Papers

Paper	Authors	Year
Constructive Discrepancy Minimization by Walking on the Edges	Shachar Lovett, Raghu Meka	2015
Approximating Bin Packing within O(log OPT · log log OPT) Bins	Thomas Rothvoß	2013
A Logarithmic Additive Integrality Gap for Bin Packing	Rebecca Hoberg, Thomas Rothvoß	2017

Additional resources

Talk Sasho Nikolov — Discrepancy and Approximation Algorithms
Talk Nikhil Bansal — A Unified Approach to Discrepancy Minimization
Book Bansal–Nikolov — Discrepancy Theory: An Algorithmic and Geometric Perspective
Notes Sasho Nikolov — CSC2414 Lecture 10 — These notes were followed closely for the discrepancy lecture.

Module06

Geometric Packing

Shelf algorithms for two-dimensional bin packing, including NFDH and Caprara’s harmonic two-stage method, followed by the Round-and-Approx framework.

NFDH Caprara HDH Round-and-Approx

Resources

Papers

Paper	Authors	Year
Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms	E. G. Coffman Jr., M. R. Garey, D. S. Johnson, R. E. Tarjan	1980
Packing d-Dimensional Bins in d Stages	Alberto Caprara	2008
A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing	Nikhil Bansal, Alberto Caprara, Maxim Sviridenko	2009

Additional resources

Module07

Beyond Worst-Case Analysis

IID, random-order, and AOS models, with foundations from random-order algorithms and prophet inequalities, followed by applications to bin packing.

IID models Random order AOS models

Resources

Papers

Paper	Authors	Year
Random-Order Models	Anupam Gupta, Sahil Singla	2020
Recent Developments in Prophet Inequalities	José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, Tjark Vredeveld	2019
Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing	E. G. Coffman Jr., Costas Courcoubetis, M. R. Garey, D. S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis	2002
Best Fit Bin Packing with Random Order Revisited	Susanne Albers, Arindam Khan, Leon Ladewig	2021
Bin Packing under Random-Order: Breaking the Barrier of 3/2	Anish Hebbar, Arindam Khan, K. V. N. Sreenivas	2024

Additional resources

Module08

Hypergraph matching and fair allocation

Haxell's Matching Theorem, the Santa Claus problem, and the Erdős Matching Conjecture, with connections to discrete fair division.

Hypergraph matching Santa Claus Fair allocation

Module09

Graph coloring and packing

Theorems of Hajnal–Szemerédi and Sauer–Spencer, and the broader relationship between equitable colorings, embeddings, and packing phenomena.

Equitable coloring Graph packing Extremal combinatorics

Module10

Connectivity and equitable structure

The Győri–Lovász theorem and equitability under matroid constraints, highlighting structural decompositions with algorithmic and fair-division interpretations.

Graph connectivity Matroid constraints Equitability

Module11

Sperner's lemma and topological methods

Applications of Sperner's Lemma, including equitable division under non-monotone set functions and Monsky's theorem.

Topological combinatorics Sperner's lemma Monsky's theorem

References

Combinatorial optimization

B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2012.
A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, 2003.

Approximation and online algorithms

D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms .
A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 2005.

Geometry and topology

J. Matoušek, Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Springer, 2007.
M. de Longueville, A Course in Topological Combinatorics, Springer, 2013.
Topological combinatorics notes
Discrepancy lecture notes

Course logistics

Grading scheme

10% Class participationActive engagement in lectures and discussions.

30% Paper presentation and reportPresentation of a selected research paper(s), accompanied by a written report.

60% Project presentation and reportA substantial course project, culminating in a presentation and written report.

Important dates

22 & 24Sept.

Paper presentations

30 minutes presentation.

17 & 19Nov.

Project presentations

45 minutes presentation.

Microsoft Teams

Use this code to join the course team.

dwhkbzg