Advanced -> Approximation And Relaxation
Approximation ratios, LP/SDP relaxations, primal-dual methods, and the boundary between exact and near-optimal algorithms.
- Topic slug:
advanced/approximation-and-relaxation
- Tutorial page: Open tutorial
- Ladder page: Open ladder
- Repo problems currently tagged here:
0
- Repo companion pages:
2
- Curated external problems:
5
Microtopics
- approximation-ratio
- LP-relaxation
- SDP-relaxation
- randomized-rounding
- primal-dual-method
- integrality-gap
- local-search
- inapproximability
Learning Sources
Follow-Up Reading
Repo Companion Material
Curated External Problems
Core
| Problem |
Source |
Difficulty |
Context |
Style |
Prerequisites |
Tags |
Why it fits |
| Problem Set 1 |
Dartmouth EO249 |
Theory |
Approximation Algorithms |
- |
- |
TSP; Cycle Cover; Euler Tour |
Great starter set for approximation constructions around TSP-style problems. |
| Problem Set 2 |
Dartmouth EO249 |
Theory |
Approximation Algorithms |
- |
- |
Set Cover; Submodular; Greedy Approximation |
Covers several core greedy-approximation paradigms in one assignment. |
| Problem Set 4 |
Dartmouth EO249 |
Theory |
Approximation Algorithms |
- |
- |
Facility Location; Integrality Gap; LP Relaxation |
Strong LP-gap and approximation-ratio practice. |
| Problem Set 5 |
Dartmouth EO249 |
Theory |
Approximation Algorithms |
- |
- |
Knapsack PTAS; Iterated Rounding; Laminar Families |
A particularly rich set on relaxation, rounding, and structure in approximation. |
| Problem Set 6 |
Dartmouth CS 49/149 |
Theory |
Approximation Algorithms |
- |
- |
Duality; Randomized Rounding; LP |
Excellent follow-up for duality and randomized-rounding based approximation design. |
Repo Problems
No repo problem note is attached yet. Use the repo companion material above for this theory/process-heavy topic.
Regeneration
python3 scripts/generate_problem_catalog.py