19.15 Greedy Approximation

Many approximation algorithms are built around a simple principle: make the best local decision available at each step. This strategy is known as the greedy approach.

Greedy algorithms are attractive because they are usually easy to understand, simple to implement, and computationally efficient. For some problems, greedy choices produce optimal solutions. For others, they do not. Even when optimality is impossible, however, a carefully designed greedy strategy can often provide strong approximation guarantees.

Some of the most important approximation algorithms in computer science are greedy algorithms. Set Cover, facility location, scheduling, and many resource-allocation problems rely on this approach.

This section examines how greedy approximation algorithms are designed and analyzed.

Problem

Suppose an optimization problem is too expensive to solve exactly.

An exhaustive search might require:

O(2ⁿ)

or:

O(n!)

time.

You need a faster solution.

A common strategy is:

Repeatedly choose
the most beneficial action
available right now.

The challenge is determining whether those local decisions lead to a globally good solution.

Greedy Philosophy

A greedy algorithm never revisits earlier decisions.

At each step:

1. Evaluate available choices.
2. Select the best one according to a rule.
3. Commit permanently.
4. Continue.

Example:

Remaining options
→
Choose best
→
Repeat

The algorithm does not backtrack.

This simplicity often produces excellent performance.

Example: Maximum Value Selection

Suppose we must choose three items.

Values:

Item	Value
A	20
B	15
C	12
D	8
E	5

Greedy strategy:

Choose highest value first.

Selections:

A
B
C

Total:

47

For this simple problem, the greedy choice is clearly optimal.

More interesting problems impose constraints that make analysis necessary.

Set Cover

Set Cover is one of the most famous approximation problems.

Given:

Universe U

and a collection of subsets:

S₁, S₂, ..., Sₖ

select the fewest subsets whose union covers all elements.

Example:

U = {1,2,3,4,5,6}

Subsets:

S1 = {1,2,3}
S2 = {2,4}
S3 = {3,4,5}
S4 = {5,6}
S5 = {6}

Goal:

Cover all elements
using as few sets as possible.

Finding the optimal solution is computationally difficult.

Greedy Set Cover

Greedy rule:

Choose the set
covering the largest number
of uncovered elements.

Algorithm:

1. Mark all elements uncovered.
2. Select the set covering the most uncovered elements.
3. Mark those elements covered.
4. Repeat until everything is covered.

def greedy_set_cover(
    universe: set[int],
    sets: list[set[int]],
) -> list[set[int]]:

    uncovered = set(universe)
    chosen = []

    while uncovered:
        best = max(
            sets,
            key=lambda s: len(
                s & uncovered
            ),
        )

        chosen.append(best)
        uncovered -= best

    return chosen

The implementation is remarkably simple.

Example Execution

Universe:

{1,2,3,4,5,6}

Available sets:

{1,2,3}
{2,4}
{3,4,5}
{5,6}

First choice:

{1,2,3}

covers three elements.

Remaining:

{4,5,6}

Second choice:

{3,4,5}

covers two new elements.

Remaining:

{6}

Third choice:

{5,6}

covers the final element.

Solution:

3 sets

Whether this is optimal depends on the instance.

The approximation guarantee applies regardless.

Approximation Ratio of Greedy Set Cover

A remarkable theorem states:

Greedy Set Cover
is an H(n)-approximation

where:

H(n)
=
1 + 1/2 + 1/3 + ... + 1/n

is the nth harmonic number.

Asymptotically:

H(n)
≈ ln(n)

Therefore:

Approximation ratio
=
O(log n)

This is one of the most famous approximation results.

Why the Harmonic Number Appears

Suppose:

OPT

sets are sufficient to cover all remaining elements.

Then one of those sets must cover at least:

RemainingElements / OPT

elements.

The greedy algorithm always chooses a set at least that good.

Each iteration removes a significant fraction of uncovered elements.

Analyzing this process produces the harmonic-series bound.

The proof is elegant and appears frequently in approximation theory.

Weighted Set Cover

Real systems often assign costs.

Example:

Set	Cost
S1	5
S2	2
S3	10
S4	3

Choosing the largest set may be inefficient.

Instead use:

Cost per newly covered element

Greedy rule:

cost(set)
--------------------
newly covered items

Choose the minimum ratio.

This modification preserves strong approximation guarantees.

Scheduling Example

Suppose jobs have deadlines and profits.

Job	Deadline	Profit
A	1	100
B	2	50
C	2	40
D	1	20

Greedy strategy:

Sort by profit descending.

Schedule each job in the latest available slot.

This algorithm produces an optimal solution for the classic job sequencing problem.

This illustrates an important lesson:

Some greedy algorithms
are approximations.

Some are exact.

The difference depends on problem structure.

Facility Location Intuition

Suppose stores must serve customers.

Opening a store costs money.

Serving distant customers costs money.

Exact optimization is difficult.

Greedy approximations often repeatedly choose:

Facility producing
the largest cost reduction.

Such algorithms frequently achieve provable constant-factor approximations.

Many practical logistics systems rely on this idea.

Coverage Maximization

Consider a maximization problem.

Goal:

Select k locations
covering as many customers
as possible.

Greedy strategy:

Repeatedly select
the location providing
the largest marginal gain.

A famous theorem proves:

Greedy achieves
(1 - 1/e)
≈ 63.2%

of optimal.

This ratio appears throughout machine learning, sensor placement, advertising, and recommendation systems.

Marginal Gain

Many greedy approximations use marginal gain.

Instead of asking:

How good is this option?

ask:

How much additional benefit
does this option provide
given previous choices?

Example:

Current coverage:
100 users

Option A:
covers 30 new users

Option B:
covers 10 new users

Greedy chooses A.

Marginal gain is one of the central concepts in modern approximation algorithms.

Local Decisions vs Global Quality

The success of greedy approximation depends on a relationship between:

Local benefit

and:

Global objective

When that relationship is strong, greedy performs well.

When it is weak, greedy can perform poorly.

Understanding that distinction is a major theme in approximation theory.

Runtime Advantages

Greedy algorithms are often extremely fast.

Example:

Method	Complexity
Exhaustive search	O(2ⁿ)
Dynamic programming	Often polynomial but large
Greedy approximation	Often O(n log n)

This gap explains their popularity.

Large systems frequently prioritize scalability over perfect optimality.

Real-World Applications

Greedy approximation appears in:

• Set cover
• Feature selection
• Sensor placement
• Advertisement allocation
• Network monitoring
• Cache placement
• Facility location
• Influence maximization
• Resource scheduling
• Cloud capacity planning

Many industrial optimization systems use greedy methods as a first-line solution.

Common Proof Strategy

Approximation proofs often follow this pattern:

1. Define a measure of progress.
2. Show each greedy step achieves substantial progress.
3. Compare that progress to the optimal solution.
4. Sum over all iterations.
5. Derive the approximation ratio.

The resulting proof usually does not require computing the optimum explicitly.

Instead, it relies on structural properties of the problem.

Common Mistakes

Assuming Greedy Is Always Optimal

A greedy algorithm may produce excellent solutions while still being suboptimal.

Approximation guarantees matter.

Using the Wrong Objective

A locally attractive metric may not align with the global objective.

Choosing the correct greedy criterion is critical.

Ignoring Marginal Effects

The value of a choice often depends on previous selections.

Marginal gain usually matters more than absolute gain.

Confusing Empirical Performance with Guarantees

A greedy algorithm may perform extremely well in practice.

Approximation ratios describe worst-case behavior.

The two are not the same.

Discussion

Greedy approximation algorithms occupy an important middle ground between exact optimization and unrestricted heuristics. They retain the simplicity and efficiency of greedy decision-making while providing mathematically rigorous guarantees on solution quality. The resulting algorithms often scale to problems that are far beyond the reach of exact methods.

Many of the most influential approximation results in computer science are greedy algorithms. Set Cover achieves a logarithmic approximation factor. Coverage maximization achieves the famous (1 - 1/e) guarantee. Facility location, scheduling, and resource-allocation problems frequently admit similarly elegant solutions.

The next section examines Set Cover approximation in greater depth, using it as a complete case study in approximation analysis, harmonic bounds, and greedy algorithm design.