The Primal-Dual Schema: Dual Variables as a Certificate

Linear programming duality gives an exact characterization of optimality: a primal solution is optimal if and only if a dual solution of equal value exists, and the dual provides a certificate that no cheaper primal solution is possible. Approximation algorithms can use a weakened version of this idea. If an algorithm constructs a feasible primal solution and a feasible dual solution, and if the primal cost is at most a constant factor times the dual value, then the ratio is bounded, because the dual value is itself a lower bound on the optimum. The algorithm never needs to solve the LP. It runs the dual ascent and the primal construction together, and the charging relationship between them is what produces the guarantee.

Duality in the form the schema uses

For a minimization primal with non-negative costs $c$, constraints $Ax \ge b$, $x \ge 0$, the dual is

$$ \max ; b^T y \quad \text{s.t.} \quad A^T y \le c, \quad y \ge 0 $$

Weak duality says every feasible dual $y$ satisfies $b^T y \le c^T x$ for every feasible primal $x$, so the dual value is a lower bound on the optimum. Complementary slackness says that at optimality, a primal variable can be positive only if its dual constraint is tight, and a dual variable can be positive only if its primal constraint is tight.

The primal-dual schema turns this into an algorithm design pattern with three components:

1. A dual ascent phase that raises dual variables monotonically, maintaining dual feasibility, until some dual constraint becomes tight. The variable that becomes tight corresponds to a primal object that is now affordable.
2. A primal construction phase that takes the primal objects whose dual constraints are tight, and repairs the result into a feasible primal solution.
3. A charging argument that assigns the cost of every primal object to dual variables, showing total primal cost is at most $\alpha$ times the dual objective.

The third step is where the ratio appears. It is not derived from an LP solver’s output but from an invariant maintained during the ascent.

Facility location as the worked case

Facility location: $m$ facilities, each with opening cost $f_i$; $n$ clients, each with connection cost $c_{ij}$ to facility $i$. Open a set of facilities and connect every client to an open one, minimizing opening plus connection cost. The LP relaxation is

$$ \min \sum_i f_i y_i + \sum_{i,j} c_{ij} x_{ij} \quad\text{s.t.}\quad \sum_i x_{ij} \ge 1 \ \forall j, \quad x_{ij} \le y_i, \quad x, y \ge 0 $$

The dual has variables $\alpha_j \ge 0$ for the client constraints and $\beta_{ij} \ge 0$ for the connection constraints, with $\sum_j \beta_{ij} \le f_i$ and $\alpha_j - \beta_{ij} \le c_{ij}$. The dual objective is $\sum_j \alpha_j$, which has a natural reading: each client’s $\alpha_j$ is how much it is willing to pay toward being connected.

The ascent raises all $\alpha_j$ simultaneously from zero. As $\alpha_j$ grows, the constraint $\alpha_j - \beta_{ij} \le c_{ij}$ forces $\beta_{ij}$ upward when $\alpha_j$ exceeds $c_{ij}$, and the facility budget $\sum_j \beta_{ij} \le f_i$ limits how far this can go. When some facility’s budget becomes exhausted, its constraint is tight, and the algorithm opens it and connects every client $j$ with $\alpha_j \ge c_{ij}$ to it. Those clients are then frozen: their $\alpha$ stops rising.

Two phases follow. Clients connected in the ascent are assigned to the facility that paid for them. Clients left unconnected have $\alpha_j$ still below their connection cost to every opened facility; for these, the algorithm opens the cheapest facility within reach, paying its opening cost, and connects them. The total cost is bounded by the sum of the frozen $\alpha$ values plus the opening costs of facilities opened in the second phase.

The charging is the delicate part. Each opened facility’s opening cost is charged to the clients whose $\alpha$ values paid for it, and the total charged is at most the facility’s cost, because the budget constraint was tight at the moment of opening. Clients connected in the second phase are charged their own $\alpha$ plus the opening cost of one facility, and the factor of 3 comes from showing that each such client’s charge is at most three times its own $\alpha$. Making that bound hold requires care with the “first connection” and “second connection” events. A related line of work replaces the charging argument with dual fitting analyzed through a factor-revealing linear program, and that analysis lowers the factor to about 1.61.

def facility_primal_dual(f, c):
    # f[i]: opening cost of facility i; c[i][j]: cost to connect client j to i
    m, n = len(f), len(c[0])
    alpha = [0.0] * n            # dual variable per client
    paid = [0.0] * m             # dual budget spent on each facility
    opened = [False] * m
    assigned = [None] * n
    paying = lambda i: sum(1 for j in range(n)
                           if assigned[j] is None and alpha[j] >= c[i][j])
    while True:
        delta = float('inf')     # next event: a client starts paying, or a budget empties
        for i in range(m):
            if opened[i]:
                continue
            for j in range(n):
                if assigned[j] is None and alpha[j] < c[i][j]:
                    delta = min(delta, c[i][j] - alpha[j])
            if paying(i):
                delta = min(delta, (f[i] - paid[i]) / paying(i))
        if delta == float('inf'):
            break
        for j in range(n):
            if assigned[j] is None:
                alpha[j] += delta
        for i in range(m):
            if opened[i]:
                continue
            paid[i] += delta * paying(i)
            if paid[i] >= f[i] - 1e-9:   # budget exhausted: open and freeze clients
                opened[i] = True
                for j in range(n):
                    if assigned[j] is None and alpha[j] >= c[i][j]:
                        assigned[j] = i
    for j in range(n):                   # phase two: connect the rest
        if assigned[j] is None:
            i = min(range(m), key=lambda k: c[k][j])
            opened[i] = True
            assigned[j] = i
    return opened, assigned

The event computation is where an implementation earns its care: it must take the minimum over all unassigned clients of the gap to the next connection cost, and over all unopened facilities of the remaining budget divided by the number of clients currently paying into it. Overshooting any event breaks dual feasibility, and the charging argument depends on each facility’s budget being exactly exhausted at the moment it opens. The structure is the point: the decision to open a facility is taken inside the ascent, driven by the dual budget, rather than by a separate pass over the instance; only the clients that the ascent could not place are left for the second pass.

Why the LP solver is not needed

Solving the facility location LP directly with a general solver and rounding the result does not give the same guarantee on its own. The relaxation’s integrality gap is bounded but strictly above 1, so a rounding rule that reads only the LP value still needs an argument specific to the rounding and to the structure of the relaxation. The dual-ascent algorithm sidesteps that sensitivity by constructing a particular dual solution, one that the primal construction can charge against. The guarantee is then a statement about that dual solution’s relationship to the primal one, not about the LP optimum.

This is the general advantage of the schema. It produces combinatorial algorithms with no LP solver, and the analysis is self-contained: the dual solution is built by the algorithm itself, so its value is known without solving anything. The disadvantage is that each problem needs its own ascent rule and its own charging argument; there is no generic primal-dual algorithm that works for arbitrary LPs with a bounded ratio.

Dual fitting and the difference from dual ascent

A closely related technique, dual fitting, constructs a primal solution by any heuristic and then exhibits a dual solution whose value bounds the primal cost, scaling the dual variables by a factor. If the scaled dual is feasible and its value is at least $1/\alpha$ times the primal cost, the ratio is $\alpha$.

The set cover analysis in the harmonic bound can be presented this way. Assign each element $e$ a dual variable equal to the cost per new element of the set that covered it, divided by $H(n)$. The dual constraint for each set says that the sum of its elements’ variables is at most the set’s cost, and the harmonic factor is exactly what makes that constraint hold. The primal cost is then at most $H(n)$ times the dual value, giving the ratio without an ascent phase at all.

Dual fitting is weaker in one respect: it requires knowing the primal solution first, so the dual is constructed after the fact and cannot guide the algorithm. Dual ascent is stronger: the dual drives the primal construction, and the algorithm’s decisions are made by the ascent. For problems where a good heuristic is already known and only the proof is missing, dual fitting is the cheaper route.

Prize-collecting and the Lagrangian view

A useful generalization: relax a constraint by allowing violations at a penalty, and let the dual variable for that constraint be the penalty. The prize-collecting Steiner tree problem does this. Every vertex must either be spanned by the tree or pay a penalty $\pi_v$; the objective is tree cost plus penalties for excluded vertices. The LP relaxation’s dual variable for each vertex’s coverage constraint becomes the penalty, and a primal-dual algorithm that raises these variables produces a tree whose cost plus penalties is within a factor of 2 of optimal.

The Lagrangian view makes the connection explicit. Penalizing uncovered vertices converts a covering constraint into an objective term, and the optimal penalty is a Lagrange multiplier. Primal-dual ascent is a way of finding good multipliers without solving the Lagrangian optimization exactly, and the ratio bound is a statement about how much is lost by not optimizing the multipliers to convergence.

This is also why the technique extends to network design, where the constraints are cut requirements rather than element coverage. In the survivable network design problem, each pair of vertices demands a certain number of edge-disjoint paths, and the dual variables live on cuts. The ascent raises cut variables until an edge’s cost is covered, at which point the edge is bought. The analysis requires a bound on how many times each edge can be bought, which the structure of the cut requirements supplies; the primal-dual algorithm that works this way gives a factor of $2k$ when no requirement exceeds $k$. A later algorithm based on iterated rounding drops the dependence on the requirement and gives a factor of 2 for all instances. That progression is characteristic of network design: the primal-dual ratios grow with a parameter of the instance, while the best known ratios do not.

Limits of the schema

The schema gives a ratio whenever the charging argument closes, and the difficulty is entirely in closing it. Three failure modes recur.

The dual can stall. If the ascent raises variables that never become tight for any primal object, the dual value grows without contributing to a primal construction, and the ratio degrades. The fix is to raise variables in a controlled order rather than all at once.

The repair can be expensive. The primal construction phase often must repair infeasibility, and the repair’s cost may not be chargeable to the dual. In facility location the second phase opens facilities whose cost is charged to clients, and the bound depends on each such client having accumulated enough $\alpha$. If the instance has clients far from all facilities, the accumulated $\alpha$ may be small relative to the opening cost, and the argument needs the metric structure of the connection costs to close.

The integrality gap can exceed the schema’s ratio. A primal-dual algorithm with ratio $\alpha$ implies that the integrality gap of the LP it uses is at most $\alpha$, since the algorithm’s cost is at least the integer optimum and the dual value is at most the LP optimum. So a large integrality gap rules out a small ratio from this approach. The relationship is one-directional, and it is the bridge to the hardness results discussed in gap amplification and the limits of approximation: a proven integrality gap is evidence, not proof, that no polynomial algorithm achieves a better ratio, while a proven inapproximability result settles the question for all algorithms.