Fall 2026 · Graduate Topics Course

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

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 algorithmsWeight functionsNF · FF · FFD
Resources

Module 01 resources

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

Curated list
Lecture notesOne combined instructor-prepared set of notes
Lecture notes 1: Greedy bin-packing algorithms and weight-function analysisA unified treatment of Next Fit, First Fit, First Fit Decreasing, asymptotic guarantees, and weight-function certificates.Link to be added
Relevant papersFoundational and topic-specific research papers
Johnson et al. — Worst-Case Performance Bounds for Simple One-Dimensional Packing AlgorithmsClassical analysis of First Fit, Best Fit, and decreasing-order variants.CoreDósa — The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9 OPT(I) + 6/9The definitive tight asymptotic analysis of First Fit Decreasing.RecommendedCoffman, Garey & Johnson — Approximation Algorithms for Bin Packing: A SurveyHistorical and methodological background on greedy heuristics and their analysis.Reading reference
Other resourcesBackground reading, videos, animations, and interactive material
Williamson–Shmoys — Bin packing and approximation-analysis backgroundSupporting textbook material on approximation guarantees and charging arguments.BookInteractive demo: Greedy bin-packing comparison labCompare Next Fit, First Fit, Best Fit, decreasing variants, random-order Best Fit, Worst Fit, and Modified First Fit Decreasing with step-by-step animation and performance metrics.Interactive animationInteractive weight-function checkerAssign item weights and test the maximum weight of a feasible bin pattern.Interactive placeholder
Module02

Competitive Analysis and Lower Bounds

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

Competitive analysisHarmonic roundingYao lower bound
Resources

Module 02 resources

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

Curated list
Lecture notesOne combined instructor-prepared set of notes
Lecture notes 2: Competitive analysis, Harmonic rounding, and lower boundsA combined treatment of asymptotic competitive ratios, Harmonic size classes, weighting arguments, and Yao’s adversarial lower bound.Link to be added
Relevant papersFoundational and topic-specific research papers
Yao — New Algorithms for Bin PackingIntroduces Refined First Fit and proves the classical 3/2 lower bound for online bin packing.CoreLee & Lee — A Simple On-Line Bin-Packing AlgorithmThe foundational Harmonic algorithm and its size-class analysis.CoreSeiden — On the Online Bin Packing ProblemThe Super Harmonic framework and a systematic weighting-function analysis.Further reading
Other resourcesBackground reading, videos, animations, and interactive material
Borodin–El-Yaniv — Online Computation and Competitive AnalysisGeneral background on competitive analysis and adversarial models.Book referenceAnimation: Harmonic size classesExplore class boundaries, reserved capacities, and the induced packing patterns.Animation placeholderAdversarial lower-bound sandboxConstruct arrival sequences and compare an online algorithm with the offline optimum.Interactive placeholder
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 groupingAPTASSize rounding
Resources

Module 03 resources

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

Curated list
Lecture notesOne combined instructor-prepared set of notes
Lecture notes 3: Linear grouping and the bin-packing APTASA unified presentation of large–small item decomposition, linear grouping, rounded configurations, and the asymptotic approximation guarantee.Link to be added
Relevant papersFoundational and topic-specific research papers
Fernandez de la Vega & Lueker — Bin Packing Can Be Solved within 1 + ε in Linear TimeThe landmark linear-grouping approximation scheme for bin packing.CoreKarmarkar & Karp — An Efficient Approximation Scheme for the One-Dimensional Bin-Packing ProblemA configuration-LP-based refinement with a polylogarithmic additive term.RecommendedBansal, Caprara & Sviridenko — A New Approximation Method for Set Covering ProblemsUses the subset-oblivious consequences of the Fernandez de la Vega–Lueker scheme.Further reading
Other resourcesBackground reading, videos, animations, and interactive material
Williamson–Shmoys — Approximation schemes and roundingBackground on PTAS/APTAS design and rounding paradigms.BookAnimation: Linear groupingSort items, form groups, round sizes, and observe the loss introduced by grouping.Animation placeholderConfiguration enumeratorExplore feasible rounded bin configurations for a selected ε.Interactive placeholder
Module04

Separation Oracle and Iterative Rounding

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

Separation oracleConfiguration LPKarmarkar–Karp
Resources

Module 04 resources

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

Curated list
Lecture notesOne combined instructor-prepared set of notes
Lecture notes 4: Separation oracles and Karmarkar–Karp iterative roundingA combined account of the Gilmore–Gomory LP, its dual, knapsack separation, approximate optimization, and iterative rounding.Link to be added
Relevant papersFoundational and topic-specific research papers
Gilmore & Gomory — A Linear Programming Approach to the Cutting-Stock ProblemThe foundational pattern/configuration LP formulation.CoreKarmarkar & Karp — An Efficient Approximation Scheme for the One-Dimensional Bin-Packing ProblemThe central iterative-rounding and configuration-LP algorithm.CoreGrötschel, Lovász & Schrijver — The Ellipsoid Method and Its Consequences in Combinatorial OptimizationFoundational optimization–separation framework.Background
Other resourcesBackground reading, videos, animations, and interactive material
Schrijver — Combinatorial Optimization: Polyhedra and EfficiencyReference material on separation, optimization, and polyhedral methods.Book referenceAnimation: Column generation and separationShow how a violated dual constraint generates a new packing pattern.Animation placeholderIterative-rounding traceFollow the residual instance and LP solution across rounding iterations.Interactive placeholder
Module05

Discrepancy-Based Rounding

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

Lovett–MekaPartial coloringHoberg–Rothvoss
Resources

Module 05 resources

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

Curated list
Lecture notesOne combined instructor-prepared set of notes
Lecture notes 5: Discrepancy-based rounding for bin packingA combined treatment of partial coloring, the Lovett–Meka edge-walk, entropy/discrepancy rounding, and the Hoberg–Rothvoss additive-gap algorithm.Link to be added
Relevant papersFoundational and topic-specific research papers
Lovett & Meka — Constructive Discrepancy Minimization by Walking on the EdgesA constructive partial-coloring method based on a constrained random walk.CoreRothvoß — Approximating Bin Packing within O(log OPT · log log OPT) BinsIntroduces discrepancy-based rounding for the Gilmore–Gomory relaxation.RecommendedHoberg & Rothvoß — A Logarithmic Additive Integrality Gap for Bin PackingObtains an OPT + O(log OPT) algorithm through discrepancy and container packing.Core
Other resourcesBackground reading, videos, animations, and interactive material
Lovett–Meka author manuscriptFreely accessible version of the edge-walk paper.ReadingAnimation: Edge-walk partial coloringVisualize variables moving inside the polytope and freezing at ±1.Animation placeholderContainer-packing visualizerIllustrate the two-stage Hoberg–Rothvoss packing and deficiency correction.Interactive placeholder
Module06

Geometric Packing and Round-and-Approx

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

NFDHCaprara HDHRound-and-Approx
Resources

Module 06 resources

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

Curated list
Lecture notesOne combined instructor-prepared set of notes
Lecture notes 6: Geometric packing and Round-and-ApproxA combined treatment of shelf packings, NFDH, harmonic two-stage packing, geometric lower bounds, and the Round-and-Approx paradigm.Link to be added
Relevant papersFoundational and topic-specific research papers
Coffman et al. — Performance Bounds for Level-Oriented Two-Dimensional Packing AlgorithmsThe classical analysis of NFDH and related shelf algorithms.CoreCaprara — Packing Two-Dimensional Bins in HarmonyHarmonic decomposition into shelves and two-stage packing.CoreBansal & Khan — Improved Approximation Algorithm for Two-Dimensional Bin PackingDevelops the Round-and-Approx approach for 2D bin packing.CoreBansal, Caprara & Sviridenko — A New Approximation Method for Set Covering ProblemsThe general randomized Round-and-Approx framework.Recommended
Other resourcesBackground reading, videos, animations, and interactive material
Caprara — Packing d-Dimensional Bins in d StagesA broader analysis of staged geometric packing.Further readingAnimation: NFDH and harmonic shelf packingStep through sorting, shelf creation, and bin assignment.Animation placeholderRound-and-Approx simulatorRound an LP solution, inspect the residual instance, and apply the completion algorithm.Interactive placeholder
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 modelsRandom orderAOS models
Resources

Module 07 resources

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

Curated list
Lecture notesOne combined instructor-prepared set of notes
Lecture notes 7: Beyond worst-case models for online bin packingA combined introduction to IID, random-order, and AOS models; prophet inequalities; and representative beyond-worst-case analyses for bin packing.Link to be added
Relevant papersFoundational and topic-specific research papers
Gupta & Singla — Random-Order ModelsA modern survey chapter on random-order online algorithms and their relation to stochastic models.Core surveyCorrea et al. — Recent Developments in Prophet InequalitiesA concise survey of threshold policies, prophet inequalities, and modern applications.Core surveyCoffman et al. — Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin PackingFoundational IID and average-case analysis for bin packing.IID bin packingAlbers, Khan & Ladewig — Best Fit Bin Packing with Random Order RevisitedModern random-order analysis of Best Fit.Random orderHebbar, Khan & Sreenivas — Bin Packing under Random-Order: Breaking the Barrier of 3/2The first improvement below 3/2 for Best Fit in random order.Further reading
Other resourcesBackground reading, videos, animations, and interactive material
Gupta–Singla chapter in Beyond the Worst-Case Analysis of AlgorithmsPublisher page for the random-order survey chapter.Book chapterSimons Institute talks on prophet inequalities and stochastic online algorithmsVideo material connecting stopping rules, thresholds, and online optimization.VideoSimulation: Worst-case vs IID vs random orderCompare the same bin-packing heuristic under multiple arrival models.Interactive placeholder
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 matchingSanta ClausFair allocation
Resources

Module 08 resources

Lecture notes, papers, and supplementary resources will be added here.

Coming soon
Lecture notesInstructor-prepared notes and handouts
Lecture notesModule notes will be added later.Link to be added
Relevant papersResearch papers and surveys
Relevant papersA curated paper list will be added later.Link to be added
Other resourcesBackground reading, videos, and animations
Other resourcesReading materials and visual links will be added later.Link to be added
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 coloringGraph packingExtremal combinatorics
Resources

Module 09 resources

Lecture notes, papers, and supplementary resources will be added here.

Coming soon
Lecture notesInstructor-prepared notes and handouts
Lecture notesModule notes will be added later.Link to be added
Relevant papersResearch papers and surveys
Relevant papersA curated paper list will be added later.Link to be added
Other resourcesBackground reading, videos, and animations
Other resourcesReading materials and visual links will be added later.Link to be added
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 connectivityMatroid constraintsEquitability
Resources

Module 10 resources

Lecture notes, papers, and supplementary resources will be added here.

Coming soon
Lecture notesInstructor-prepared notes and handouts
Lecture notesModule notes will be added later.Link to be added
Relevant papersResearch papers and surveys
Relevant papersA curated paper list will be added later.Link to be added
Other resourcesBackground reading, videos, and animations
Other resourcesReading materials and visual links will be added later.Link to be added
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 combinatoricsSperner's lemmaMonsky's theorem
Resources

Module 11 resources

Lecture notes, papers, and supplementary resources will be added here.

Coming soon
Lecture notesInstructor-prepared notes and handouts
Lecture notesModule notes will be added later.Link to be added
Relevant papersResearch papers and surveys
Relevant papersA curated paper list will be added later.Link to be added
Other resourcesBackground reading, videos, and animations
Other resourcesReading materials and visual links will be added later.Link to be added

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

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