Greedy and Approximation Algorithms: Proofs and Limits

Greedy and Approximation Algorithms

A greedy algorithm commits to a locally preferred choice and continues with what remains. That choice can be exactly optimal, provably approximate, or simply a useful heuristic. The difference comes from a correctness or approximation argument under precise assumptions, not from how intuitive the rule feels.

Start by stating the feasible solutions and objective. Then ask what property lets a local choice preserve an optimal solution, or what lower bound relates the constructed result to an optimum. Small counterexamples are an efficient way to discover which claim you can actually defend.

TL;DR

State objective, feasibility, weights, and tie behavior first.
Use an exchange or structural argument for an exact greedy rule.
State approximation ratios with minimization/maximization direction and assumptions.
Use exhaustive small cases to find defects, while retaining a separate general proof.
Revisit the argument when weights, deadlines, or constraints change.

Quick Example

This complete Python example selects the maximum count of nonoverlapping positive-length half-open intervals by finish time. A separate routine chooses both endpoints of a greedy matching to cover an unweighted graph’s edges.

The block passed, and additional bounded oracle checks passed for all 32 subsets of five intervals and all 64 simple graphs on four vertices. These finite checks do not prove a theorem for every input. The graph routine assumes an ordinary undirected unweighted graph; weighted objectives and other constraints need a different argument.

Core Concepts

Exact greedy choice

An exchange argument starts with an optimal solution and replaces part of it with the greedy choice without making the result worse or infeasible. MIT’s minimum-spanning-tree notes illustrate this through a least-weight crossing edge and a cut argument. Greedy-choice proof

Approximation

For unweighted vertex cover, taking both endpoints of a maximal matching gives a factor-two minimization bound: any cover must choose at least one endpoint of each disjoint matched edge. Approximation analysis

Heuristic

A heuristic can be useful without a proven ratio. Describe its observed quality under the tested workload and avoid promoting that observation into a worst-case guarantee.

Prove the interval choice and identify its boundary

For the example’s interval-count problem, choose the interval with the earliest finishing time. Consider an optimal schedule’s first interval. Replacing it with the greedy interval cannot finish later, so the remaining intervals in that schedule still have room to start. Repeat the reasoning on the remaining compatible intervals.

The proof depends on the objective: number of accepted intervals, with one compatible resource and no weights. If one long interval is worth more than several short ones, maximizing count can fail to maximize value. The original rule has not become buggy; the optimization problem has changed.

Endpoint policy also matters. The example treats [start, finish) as half-open, so an interval ending at two can be followed by one starting at two. Closed occupied endpoints or setup times require different compatibility logic and a corresponding argument.

Try a tempting incorrect rule. Choosing the earliest-starting interval from (0,5), (0,2), (2,4), and (4,6) can keep the long first interval and lose the three-interval schedule. A counterexample makes the missing property visible more quickly than repeatedly tuning a tie breaker.

Keep input validity explicit. The demonstration rejects intervals with finish no greater than start. A real application should validate the complete input before consuming results and define how malformed data is reported.

Read the ratio in the correct direction

For the matching-based cover, the selected edges share no vertices. Any cover needs an endpoint from each, so their count is a lower bound on the optimum. Taking both endpoints costs twice that lower bound and covers every edge once the matching is maximal. This is the substance of the bound, not a claim that the result is always exactly twice optimal.

Do not confuse maximal with maximum. A maximal matching cannot be extended by another disjoint edge; it need not contain the greatest possible number of edges. The approximation argument uses maximality to ensure coverage and disjointness to obtain the lower bound.

Weights change the cost relationship. Selecting both endpoints of an arbitrary edge can be expensive under arbitrary vertex weights, so the same size argument does not establish a factor-two weighted-cost result. Choose an algorithm and proof for the actual problem.

Use implementation checks without replacing the proof

A small exhaustive oracle is useful when the objective can be computed directly for tiny inputs. Enumerate feasible solutions, calculate their objective, and compare the candidate. Include empty inputs, ties, duplicates where permitted, and adversarial orderings.

The extra checks for this article enumerate bounded interval subsets and four-vertex simple graphs. They support confidence in the implementation for those cases and can expose a coding defect. They do not cover arbitrarily many vertices, numeric overflow, malformed input, or every extension of the model.

Separate the algorithm’s mathematical complexity from the costs of its representation. Sorting intervals, storing graph edges, validating input, and materializing the answer all contribute. State whether ordering is supplied or computed and whether memory fits the workload.

For a heuristic chosen for operating simplicity, measure solution quality against a suitable baseline or lower bound on representative instances. Record cases where it performs poorly. If constraints change, rerun both correctness and quality checks.

Adopt a greedy rule when its proof fits the task or its measured tradeoff is acceptable and honestly described. When the rule fails, reconsider dynamic programming, search, flow, optimization, or another method appropriate to the actual structure.

Best Practices

Write the model first

State feasible inputs, objective, endpoint or weight semantics, and output requirements before choosing a local rule.

Keep a counterexample set

Preserve small cases that defeat plausible wrong choices. Use them when refactoring or extending the algorithm.

Maintain the argument

Link implementation invariants to the proof and update both when the problem changes.

Common Mistakes

Bad: A plausible greedy choice must be optimal.

Correct: Provide an exchange/structural argument or label the method as a heuristic.

Bad: A factor-two bound means the answer is always twice optimum.

Correct: It is an upper bound for the declared minimization problem, not an equality.

Bad: Small exhaustive tests prove every input.

Correct: Use them as bounded implementation evidence beside the general mathematical argument.

FAQ

Can an approximation return an optimal result?

Yes. The guarantee bounds the worst permitted result; many instances can be solved exactly by the same algorithm.

Does the vertex-cover example support arbitrary weights?

No. Its proof uses vertex counts in an unweighted undirected graph.

When should I stop trying greedy rules?

When the needed structural property does not hold or counterexamples violate the required quality. Choose a method suited to the objective and constraints.