LP and Flow Connections
Video walkthrough: Programmers and Artists — Greedy Sweep with Lagrangian Relaxation
This lesson connects the greedy sweep line from Chapter 4 (Assignment Problems) to the deeper mathematical machinery: Linear Programming, Lagrangian Relaxation, Min-Cost Max-Flow, and the boundary where greedy stops working.
If you haven't solved the CSES Programmers and Artists problem yet, do that first — this lesson explains why the algorithm works, not how to code it.
The LP Formulation
The assignment problem (select exactly \(a\) programmers and \(b\) artists to maximize total skill) can be written as an integer program:
subject to: - \(x_i + y_i \leq 1\) for all \(i\) (each person gets at most one role) - \(\sum x_i = a\) (exactly \(a\) programmers) - \(\sum y_i = b\) (exactly \(b\) artists) - \(x_i, y_i \in \{0, 1\}\)
Why the Geometry Works: LP Meets the Sweep Line
In Linear Programming, constraints define a feasible region (a polytope), and the objective function defines a direction. The optimal solution sits at a vertex of the polytope.
For our 2D applicant plot (X = programming skill, Y = artistic skill), the diagonal line \(A = P - C\) is literally the level set of the LP objective — all points on the line contribute equally to the objective. Sweeping the line downward is equivalent to sweeping the LP objective across the feasible region.
When the constraint matrix is totally unimodular (TUM), the LP vertices are always integers — so the geometric sweep finds the exact integer optimum without rounding. This is why the exchange argument produces an optimal greedy for two-role assignment.
Lagrangian Relaxation: Shattering the Global Constraint
Attach multipliers \(\lambda\) (penalty for programming) and \(\mu\) (penalty for art) to the count constraints:
For fixed \(\lambda\) and \(\mu\), the global problem shatters into independent subproblems. Each applicant independently chooses their best role based on "shifted skills":
- Hire as Programmer: if \((P_i - \lambda) > 0\) and \((P_i - \lambda) > (A_i - \mu)\)
- Hire as Artist: if \((A_i - \mu) > 0\) and \((A_i - \mu) > (P_i - \lambda)\)
- Reject: if both shifted skills are \(\leq 0\)
The boundary where an applicant switches from programmer to artist is \((P_i - \lambda) = (A_i - \mu)\), which simplifies to \(P_i - A_i = \lambda - \mu = C\), a single combined penalty constant.
This is exactly WQS Binary Search from Lesson 1 — the penalty \(C\) plays the same role as \(\lambda\) in the Alien's Trick. The sweep line evaluates all possible values of \(C\) simultaneously.
Worked Example: Perfect Penalties
4 applicants, need \(a=2\) programmers and \(b=1\) artist:
| Applicant | \(P_i\) | \(A_i\) | \(D_i = P_i - A_i\) |
|---|---|---|---|
| 0 | 8 | 3 | 5 |
| 1 | 6 | 7 | -1 |
| 2 | 5 | 2 | 3 |
| 3 | 3 | 9 | -6 |
With \(\lambda = 3\) and \(\mu = 5.5\), the shifted skills are:
| Applicant | \(P_i - \lambda\) | \(A_i - \mu\) | Decision |
|---|---|---|---|
| 0 | 5 | -2.5 | Programmer (\(5 > -2.5\) and \(5 > 0\)) |
| 1 | 3 | 1.5 | Programmer (\(3 > 1.5\) and \(3 > 0\)) |
| 2 | 2 | -3.5 | Programmer (\(2 > -3.5\) and \(2 > 0\)) |
| 3 | 0 | 3.5 | Artist (\(3.5 > 0\) and \(3.5 > 0\)) |
That gives 3 programmers, but we only need 2. The combined constant \(C = \lambda - \mu = -2.5\). The sweep line naturally finds this boundary: applicants with \(D_i > C\) are programmers, those with \(D_i < C\) are artists. The heaps then select the best 2 from the programmer-leaning group and the best 1 from the artist-leaning group.
The sweep line algorithm evaluates all possible values of \(C\) simultaneously — you never need to guess \(\lambda\) and \(\mu\) separately.
Network Flow (MCMF) Model
The same problem has a clean min-cost max-flow formulation:
- Source \(S\) → each Applicant \(U_i\): capacity 1, cost 0
- Applicant \(U_i\) → Programmer Node \(N_P\): capacity 1, cost \(-P_i\) (negate for maximization)
- Applicant \(U_i\) → Artist Node \(N_A\): capacity 1, cost \(-A_i\)
- Programmer Node \(N_P\) → Sink \(T\): capacity \(a\), cost 0
- Artist Node \(N_A\) → Sink \(T\): capacity \(b\), cost 0
Push exactly \(a + b\) units of flow. The negated total cost is the maximum skill sum. Complexity: \(O(n^2)\) with SPFA-based augmentation, but the greedy sweep is faster at \(O(n \log n)\).
What Breaks If There Are Three Roles?
Suppose you add a third role — "designer" with skill \(G_i\), needing exactly \(c\) designers. Now the exchange argument doesn't produce a single sort key. Swapping a programmer and a designer gives one inequality; swapping an artist and designer gives another. You can't linearize all pairs into a 1D sort.
This is where TUM breaks down. With three or more roles, the LP relaxation can have fractional optima, and greedy fails. You need MCMF or DP.
The boundary to remember: Two roles → greedy works (TUM). Three roles → greedy fails (LP is fractional). Recognizing this saves you from chasing a greedy that doesn't exist.
When LP Fails Completely: Unbounded 2-Item Knapsack
Here's a problem where LP intuition leads you astray.
Treasure Chest problem: Unlimited emeralds (weight \(w_1\), value \(v_1\)) and sapphires (weight \(w_2\), value \(v_2\)). Capacity \(W\). Maximize total value.
The Trap: "Pick the item with better value-per-weight ratio." This is the LP relaxation's answer. But the integer constraint makes it wrong.
Example: \(w_1=3\), \(v_1=4\), \(w_2=5\), \(v_2=7\). Capacity \(W=11\). - Greedy (ratio \(v_2/w_2 = 1.4 > v_1/w_1 = 1.33\)): 2 sapphires = weight 10, value 14. Remaining 1, nothing fits. Total = 14. - Better: 1 sapphire + 2 emeralds = weight 11, value 15. Greedy missed it.
The \(O(\sqrt{W})\) trick: you never need more than \(w_1 - 1\) copies of item 2. If you have \(w_1\) copies (weight \(w_1 \cdot w_2\)), replace with \(w_2\) copies of item 1 (same weight). One option is always at least as good. Iterate count2 from \(0\) to \(\min(W/w_2,\; w_1 - 1)\).
Why WQS and LP fail here: The constraint matrix is NOT TUM. There are no concave marginal gains — adding one more sapphire always gives exactly \(v_2\). The answer function is not concave in \(k\), so the tangent-line trick of WQS does not apply.
The Full Picture
| Structure | Greedy works? | Why |
|---|---|---|
| Two-role assignment | Yes | TUM → LP integrality → exchange argument |
| Three-role assignment | No | LP is fractional → need MCMF |
| Non-adjacent K picks | Yes (with undo) | Concave \(h(k)\) → WQS / Slope Trick |
| Unbounded knapsack | No | No concavity → LP rounds badly |
| Matroid structures | Yes | Exchange property → pure greedy |
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CSES — Programmers and Artists | cses.fi/problemset/task/2426 | Hard |
| ABC 216G — 01Sequence | atcoder.jp/contests/abc216/tasks/abc216_g | 600pts |