Skip to content

Advanced -> Optimization And Duality

LP duality, convex relaxation, and the optimization language that later feeds into flow, DP tricks, and aliens-style reasoning.

  • Topic slug: advanced/optimization-and-duality
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 2
  • Repo companion pages: 2
  • Curated external problems: 6

Microtopics

  • LP-duality
  • complementary-slackness
  • convex-relaxation
  • Lagrangian-relaxation
  • KKT-conditions
  • subgradient-methods
  • primal-dual-schema
  • aliens-trick

Learning Sources

Source Type
Stanford EE364a Course
Boyd-Vandenberghe Convex Optimization Reference
Stanford CS261 Course

Follow-Up Reading

Source Type
EE364a duality notes Course
EE364b Course
MS&E 310 Conic Linear Optimization Course

Repo Companion Material

Material Type
Police Chase note bridge note
Maximum Flow tutorial adjacent tutorial

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Giant Pizza CSES Medium - Logical Modeling 2-SAT; Implication Graphs 2-SAT; Constraint Satisfaction A good example of optimizing by encoding constraints into a solvable dual structure.
Police Chase CSES Medium - - - Minimum Cut; Certificate; Flow Dual Makes the cut side of flow duality explicit.
School Dance CSES Medium - Augmenting Paths Bipartite Matching Matching; Bipartite Graphs; Flow; Bipartite Graph A very approachable gateway into max-flow / matching duality.
Distinct Routes CSES Hard - - - Edge-Disjoint Paths; Flow Decomposition; Packing A strong path-packing formulation that broadens optimization modeling.

Challenge

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Download Speed CSES Hard - Flow Modeling Max Flow; Min Cut Max Flow; Min Cut; Network Optimization; Duality Intuition Max-flow/min-cut duality is the core lesson of this problem.
Task Assignment CSES Hard - Exact Optimization Matching; Cost Matrices Assignment; Min-Cost Optimization; Min-Cost Flow; Bipartite Optimization A textbook assignment problem with a natural dual interpretation.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
C11XU Bộ sưu tập đồng xu secondary hard xor-independence; forest selection; augmenting exchange Note Code
POLICECHASE Police Chase secondary medium unit capacity max flow; residual reachable cut; minimum edge cut certificate Note Code

Regeneration

python3 scripts/generate_problem_catalog.py