14.18 Local vs Global Optimum

Greedy algorithms are attractive because they make local decisions. At each step, the algorithm chooses the best-looking option available at that moment and commits to it. When the problem has the right structure, those local choices accumulate into a globally optimal solution.

When the structure is absent, greedy algorithms fail.

This distinction is central to greedy design. A local optimum is the best choice within the immediate neighborhood of the current state. A global optimum is the best solution among all feasible solutions. Greedy algorithms are correct only when the path of local optima is guaranteed to reach a global optimum.

This recipe explains the difference, shows how local reasoning can fail, and gives practical tests for deciding whether a greedy strategy is trustworthy.

Problem

Given an optimization problem, determine whether repeatedly choosing the best local option is sufficient to produce a globally optimal solution.

A typical greedy rule has the form:

At each step, choose the candidate with the best immediate score.

But immediate score may not reflect long-term value.

Local Optimum

A local optimum is a solution that cannot be improved by a small, allowed change.

For example, suppose we are climbing a terrain map.

At every point, we move to the neighboring point with the highest elevation.

Eventually we reach a point where all nearby points are lower.

That point is a local maximum.

It may not be the highest point on the entire map.

The algorithm has optimized locally, not globally.

Global Optimum

A global optimum is the best solution over the entire feasible space.

In the terrain analogy, it is the highest point anywhere on the map.

A greedy algorithm succeeds only when local improvement steps cannot trap us at a suboptimal point.

That requirement is strong.

Most optimization problems do not satisfy it.

Example: Fractional Knapsack

Fractional knapsack has a greedy solution.

At every step:

Take the item with highest value density.

This local rule works because each unit of capacity is interchangeable.

If a solution uses a lower-density item while a higher-density item remains available, we can exchange capacity from the lower-density item to the higher-density item and improve the result.

Therefore any non-greedy allocation cannot be globally optimal.

Here the local and global objectives align.

Example: 0/1 Knapsack

Now consider the 0/1 version.

Capacity:

Items:

Item	Weight	Value	Density
A	10	60	6
B	20	100	5
C	30	120	4

A local density rule selects:

A + B

Total value:

But the optimal solution is:

B + C

Total value:

The local rule fails because items are indivisible. Selecting A consumes capacity in a way that blocks a more valuable combination.

The problem does not allow the exchange that made fractional knapsack work.

Example: Coin Change

Greedy coin change works for many familiar coin systems.

For coins:

25, 10, 5, 1

amount:

Greedy chooses:

25 + 5

which is optimal.

But greedy does not work for every coin system.

Coins:

4, 3, 1

amount:

Greedy chooses:

4 + 1 + 1

using three coins.

Optimal:

3 + 3

using two coins.

The local choice of coin 4 looks best immediately, but it leaves a poor remainder.

Why Local Choices Fail

Local choices fail when the value of a decision depends strongly on later decisions.

Common causes include:

Cause	Effect
Indivisible choices	Cannot repair bad early choices
Strong interactions	One choice changes the value of another
Hidden constraints	Feasibility depends on future structure
Noncanonical ordering	Best immediate score does not match optimal structure
No exchange property	Cannot transform optimum into greedy form

In such problems, dynamic programming, search, branch and bound, or approximation algorithms may be required.

A Useful Question

For any greedy rule, ask:

Can every optimal solution be transformed to include this local choice?

If yes, the greedy rule may be correct.

If no, the greedy rule is probably only a heuristic.

This is the difference between a proof and an intuition.

Exchange as the Bridge

Exchange arguments connect local and global optimality.

For interval scheduling, the earliest finishing interval can replace the first interval of some optimal schedule.

For Huffman coding, the two least frequent symbols can be made sibling leaves in some optimal tree.

For minimum spanning trees, the lightest edge across a cut can appear in some optimal tree.

Each case says:

The greedy local choice can be embedded into a global optimum.

That is exactly what a greedy proof must establish.

Local Improvement Is Not Enough

Some algorithms repeatedly improve a solution locally.

Example:

Swap two jobs if it improves the schedule.

This may terminate in a local optimum.

But unless every local optimum is also global, the result is not guaranteed optimal.

Greedy algorithms need more than improvement.

They need a structural guarantee that the committed choice is safe.

Recognizing Global Structure

A greedy algorithm is more plausible when the problem has at least one of these properties:

Property	Meaning
Greedy-choice property	Some optimal solution includes the greedy choice
Optimal substructure	After the choice, the remaining problem has same form
Exchange property	Non-greedy choices can be replaced safely
Monotonicity	Progress cannot make future choices better in a hidden way
Matroid structure	All weighted greedy choices are valid

The more of these properties you can prove, the stronger the greedy case becomes.

Counterexample-Driven Design

Before proving a greedy algorithm, try to break it.

Construct small examples where:

The best-looking item blocks future choices.
A slightly worse item leaves a much better remainder.
Ties resolve badly.
A late constraint invalidates an early choice.
A local repair creates a future violation.

Counterexamples are not a nuisance. They are design tools.

They help refine the greedy rule or reveal that the problem requires another technique.

Example: Choosing the Shortest Interval

For interval scheduling, a tempting rule is:

Choose the shortest interval.

Counterexample:

Interval	Start	End
A	1	4
B	4	7
C	3	5

Shortest interval:

Optimal schedule:

A + B

The local duration score fails to capture future compatibility.

The correct score is finish time, not length.

Example: Choosing Highest Profit First

For deadline scheduling with unit-time jobs, highest profit first can work when paired with latest feasible placement.

But highest profit alone is insufficient if job durations vary.

A long high-profit job may block several shorter jobs with better combined value.

This illustrates an important point:

The greedy key and the feasibility model must match.

A correct greedy rule in one problem variant may fail after a small change in constraints.

Practical Test: The First Choice

A useful proof attempt starts with only the first decision.

Ask:

What does the greedy rule choose first?
Can some optimal solution be made to choose the same thing first?
If yes, what remains after that choice?
Is the remaining problem structurally identical?
Can the argument repeat?

If this first-choice proof fails, the full greedy proof usually fails as well.

Practical Test: The Repair Step

Another test is to assume the greedy choice is absent from an optimal solution.

Then try to repair the optimal solution.

Optimal solution O does not contain greedy choice g.
Can we replace something in O with g?

The repair must preserve feasibility and objective value.

If no such repair exists, the local choice is not obviously safe.

When Greedy Is Still Useful

A greedy algorithm may be valuable even when it lacks an optimality proof.

It may provide:

A fast heuristic.
A good initial solution.
A bound for branch-and-bound.
An approximation algorithm.
A baseline for testing.

But it should be labeled correctly.

There is a major difference between:

This greedy algorithm is optimal.

and:

This greedy heuristic often works well.

Takeaway

A local optimum is the best choice in the immediate state; a global optimum is the best solution over the entire feasible space. Greedy algorithms are correct only when local choices can be proven to participate in some global optimum. Exchange arguments, greedy-choice properties, monotonicity, and matroid structure are the tools that bridge the gap. Without such a bridge, a greedy strategy may still be useful as a heuristic, but it should not be treated as an exact algorithm.