19.18 Primal-Dual Approximation

Primal-dual approximation algorithms use linear programming structure to design fast approximate solutions. The method starts from an optimization problem, writes a linear-programming relaxation, examines its dual, and then builds a solution while maintaining information about both sides.

The central idea is simple: the dual solution gives a bound on the optimum. If the algorithm constructs a feasible primal solution whose cost is at most some factor times the dual value, then the same factor bounds the approximation ratio.

This method is especially useful for covering and network-design problems, where greedy reasoning alone can hide the underlying structure.

Problem

You need to solve a minimization problem.

The exact integer program is hard.

You can write:

Primal problem:
minimize cost
subject to coverage constraints

and its dual:

Dual problem:
maximize lower bound
subject to packing constraints

The dual gives a certificate that the optimum cannot be smaller than a certain value.

The goal is to grow that certificate while constructing a feasible approximate solution.

Linear Programming Relaxation

Consider Vertex Cover.

Given an undirected graph:

G = (V, E)

choose a minimum-size set of vertices touching every edge.

Integer program:

minimize Σ xᵥ

subject to:
xᵤ + xᵥ ≥ 1       for every edge (u, v)
xᵥ ∈ {0, 1}

The relaxation replaces:

xᵥ ∈ {0, 1}

with:

xᵥ ≥ 0

or commonly:

0 ≤ xᵥ ≤ 1

Now fractional values are allowed.

The Dual

The dual introduces one variable per edge:

yₑ

Dual problem:

maximize Σ yₑ

subject to:
Σ yₑ ≤ 1          for every vertex v
over edges e incident to v

yₑ ≥ 0

Interpretation:

Each edge wants to raise money.

Each vertex has a budget limit of 1.

The total dual value is a lower bound on the optimal vertex cover cost.

Weak Duality

Weak duality says:

Any feasible dual value
≤
Any feasible primal value

For minimization problems, this means the dual is a lower bound.

If:

dual value = 10

then:

OPT ≥ 10

If an algorithm returns a solution of cost:

20

then it has proved a 2-approximation:

ALG = 20 ≤ 2 · 10 ≤ 2 · OPT

This is the primal-dual proof pattern.

Recipe: Primal-Dual Vertex Cover

Start with:

cover = ∅
yₑ = 0 for every edge

While there is an uncovered edge (u, v):

1. Increase y_(u,v) until one endpoint becomes tight.
2. Add tight endpoints to the cover.
3. Remove all edges covered by those endpoints.

For unweighted Vertex Cover, this simplifies to the matching-based 2-approximation: pick an uncovered edge and add both endpoints.

from collections.abc import Iterable

Edge = tuple[str, str]

def primal_dual_vertex_cover(edges: Iterable[Edge]) -> set[str]:
    uncovered = set(edges)
    cover: set[str] = set()

    while uncovered:
        u, v = next(iter(uncovered))

        cover.add(u)
        cover.add(v)

        uncovered = {
            (a, b)
            for (a, b) in uncovered
            if a not in cover and b not in cover
        }

    return cover

This version does not explicitly store dual variables, but the selected uncovered edges behave as the positive dual variables.

Example

Graph edges:

(A, B)
(B, C)
(C, D)
(D, E)

Select uncovered edge:

(A, B)

Add:

A, B

Covered edges removed:

(A, B)
(B, C)

Remaining:

(C, D)
(D, E)

Select:

(C, D)

Add:

C, D

All edges are now covered.

Returned cover:

{A, B, C, D}

The selected dual edges are:

(A, B)
(C, D)

They form a matching.

Every vertex cover must include at least one endpoint of each selected edge, so:

OPT ≥ 2 selected edges? 

Careful: since selected edges are disjoint, every cover must pick at least one endpoint per selected edge.

Thus:

OPT ≥ number of selected edges

The algorithm selects two vertices per selected edge:

ALG = 2 · number of selected edges

Therefore:

ALG ≤ 2 · OPT

Weighted Vertex Cover

Primal-dual reasoning becomes more valuable in weighted problems.

Each vertex has a cost:

cᵥ

Integer program:

minimize Σ cᵥ xᵥ

subject to:
xᵤ + xᵥ ≥ 1       for every edge (u, v)
xᵥ ∈ {0, 1}

Dual:

maximize Σ yₑ

subject to:
Σ yₑ ≤ cᵥ         for every vertex v
over edges e incident to v

yₑ ≥ 0

Now each vertex has a budget equal to its cost.

Recipe: Weighted Primal-Dual Vertex Cover

Algorithm:

1. Start with empty cover.
2. Start all dual variables at zero.
3. Pick an uncovered edge (u, v).
4. Increase its dual value until either u or v becomes tight.
5. Add any tight endpoint to the cover.
6. Remove edges covered by the chosen vertices.
7. Repeat.

A vertex is tight when:

sum of incident selected dual values = vertex cost

This gives a 2-approximation for weighted Vertex Cover.

Implementation Sketch

from collections import defaultdict
from dataclasses import dataclass

@dataclass(frozen=True)
class WeightedEdge:
    u: str
    v: str

def weighted_vertex_cover(
    edges: list[WeightedEdge],
    costs: dict[str, float],
) -> set[str]:
    uncovered = set(edges)
    cover: set[str] = set()
    load: dict[str, float] = defaultdict(float)

    while uncovered:
        edge = next(iter(uncovered))
        u, v = edge.u, edge.v

        slack_u = costs[u] - load[u]
        slack_v = costs[v] - load[v]
        delta = min(slack_u, slack_v)

        load[u] += delta
        load[v] += delta

        if abs(load[u] - costs[u]) < 1e-12:
            cover.add(u)

        if abs(load[v] - costs[v]) < 1e-12:
            cover.add(v)

        uncovered = {
            e
            for e in uncovered
            if e.u not in cover and e.v not in cover
        }

    return cover

This implementation focuses on the algorithmic idea. Production code should avoid floating-point tightness checks when costs are integral or rational.

Why the Approximation Is 2

Let:

C

be the returned cover.

Each chosen vertex is tight:

cᵥ = Σ yₑ

over incident edges.

So:

cost(C)
=
Σ cᵥ over v in C

becomes:

Σ over v in C
Σ yₑ incident to v

Each edge has at most two endpoints.

Therefore every dual variable is counted at most twice:

cost(C) ≤ 2Σ yₑ

By weak duality:

Σ yₑ ≤ OPT

So:

cost(C) ≤ 2OPT

That proves the 2-approximation.

Set Cover Connection

Weighted Set Cover also has a primal-dual view.

Primal:

Choose sets
so every element is covered
at minimum total cost.

Dual:

Assign prices to elements
so no set is overcharged.

Greedy Set Cover can be interpreted as repeatedly pricing uncovered elements and choosing sets when they become cost-effective.

This connection explains why many covering problems have logarithmic or constant-factor approximation algorithms.

Facility Location Connection

Facility location problems also fit naturally.

Primal decisions:

Open facilities.
Assign clients.

Dual variables:

Client contributions.

A facility opens when enough client contributions pay for it.

This “raise dual variables until a constraint becomes tight” pattern is common in network design and clustering.

General Primal-Dual Template

For a minimization problem:

1. Write an LP relaxation.
2. Write its dual.
3. Start with an infeasible or partial primal solution.
4. Maintain a feasible dual solution.
5. Raise dual variables until a primal action becomes justified.
6. Add primal objects.
7. Prove the final primal cost is bounded by a factor times the dual value.

The proof usually follows directly from weak duality and bounded overcounting.

Why This Method Works

The dual tells the algorithm what the instance can “afford.”

Instead of choosing objects only by local benefit, the algorithm grows a lower bound on the optimum. When a primal object becomes tight, the algorithm has evidence that selecting it is justified.

This produces algorithms that are greedy in behavior but LP-guided in analysis.

Complexity

The running time depends on how constraints are represented.

For the simple vertex cover implementation:

Operation	Cost
Pick uncovered edge	O(1) average
Remove covered edges	O(m) naive
Total naive cost	O(m²) worst case

With better adjacency structures, the implementation can be improved.

In many primal-dual algorithms, the mathematical design is clean, while the engineering challenge lies in maintaining tight constraints efficiently.

Common Mistakes

Do not use a primal-dual proof without verifying dual feasibility.

Do not assume every greedy algorithm has a primal-dual interpretation.

Do not forget the overcounting factor. It usually determines the approximation ratio.

Do not rely on floating-point equality for tightness in serious implementations.

Do not confuse LP relaxation optimality with integer optimality. The gap between them is exactly what approximation analysis must control.

Takeaway

Primal-dual approximation algorithms build a solution and a proof at the same time. The dual variables provide a lower bound on the optimum. The primal solution provides a feasible answer. If the algorithm can show that its primal cost is at most α times the dual value, weak duality immediately gives an α-approximation. This method is especially effective for covering, network design, facility location, and scheduling problems.