Remaining Problem After Greedy Choice - Optimal Substructure for Greedy Algorithms | OneNoughtOne

0/361

Data Structures & AlgorithmsOptimal Substructure for Greedy

Optimal Substructure for Greedy Algorithms

LevelIntermediate

Duration60 mins

TopicOptimal Substructure for Greedy

1 / 4

Remaining Problem After Greedy Choice

The Anatomy of a Greedy Decision

Every greedy algorithm follows a deceptively simple pattern: make a choice, then solve what remains. But beneath this simplicity lies a profound structural transformation. When a greedy algorithm makes its "best local choice," it doesn't just move forward—it fundamentally reshapes the problem landscape.

Understanding this transformation is crucial. The remaining problem after a greedy choice isn't arbitrary; it has specific properties that determine whether the greedy approach will succeed or fail. This page dissects the anatomy of post-choice problem states, revealing the hidden structure that makes greedy algorithms work.

What You Will Learn

By the end of this page, you will understand exactly what happens to a problem after a greedy choice is made. You'll learn to analyze the "remaining problem" structure, recognize when this structure supports greedy correctness, and identify warning signs that the remaining problem may not be well-behaved for greedy approaches.

The Greedy Decomposition Model

To understand what remains after a greedy choice, we must first formalize how greedy algorithms decompose problems. Unlike divide-and-conquer, which splits problems into multiple independent subproblems, or dynamic programming, which considers all subproblems simultaneously, greedy algorithms follow a sequential decomposition model.

The Formal Model:

Let P be an optimization problem. A greedy algorithm operates as follows:

Choose: Select element x from the available choices in P
Commit: Add x to the solution being constructed
Transform: Derive the remaining problem P' from P, given that x is in the solution
Repeat: Apply the same process to P' until no choices remain

The critical insight is in step 3: the transformation from P to P'. This isn't merely "P minus x"—it's often a fundamentally different problem with modified constraints, reduced options, and altered objective functions.

Sequential vs Parallel Decomposition

In divide-and-conquer, we split a problem into subproblems that can (conceptually) be solved in parallel—they don't depend on each other's solutions. In greedy algorithms, decomposition is inherently sequential: each subproblem depends on the choices made before it. This sequential dependency is both the strength (simplicity) and weakness (potential for globally suboptimal solutions) of greedy approaches.

Visualizing the Transformation:

Consider how different problems transform after a greedy choice:

Activity Selection: After selecting activity A that ends earliest, the remaining problem is all activities that start after A ends. The transformation eliminates conflicting activities and shifts the "legal start time" forward.
Fractional Knapsack: After taking as much as possible of the item with highest value/weight ratio, the remaining problem has reduced capacity and fewer items (or reduced quantity of one item).
Huffman Coding: After combining the two lowest-frequency symbols into a new super-symbol, the remaining problem has one fewer symbol but modified frequencies.

Each transformation fundamentally alters the problem structure while preserving the essential nature of the optimization goal.

Characterizing the Remaining Problem

The remaining problem P' after a greedy choice has several key characteristics that we must analyze to understand greedy correctness. Let's formalize these characteristics:

Five Dimensions of Remaining Problem Analysis

•Size Reduction — The remaining problem P' should be strictly smaller than P in some measurable way. This could be fewer elements, reduced capacity, smaller input size, or decreased resource availability. Without guaranteed size reduction, termination isn't assured.
•Constraint Modification — The constraints in P' may differ from P. After choosing activity A, constraints shift from "activities that don't conflict with anything" to "activities that don't conflict with A." Understanding constraint modification reveals which options remain viable.
•Objective Preservation — The objective function in P' should relate meaningfully to P's objective. Typically, if we've already accumulated value V from our greedy choice, P' optimizes the same objective with V already "banked."
•Independence — Crucially, the optimal solution to P' should be optimal regardless of how we got there. The history of choices should be summarized entirely in the current state—no hidden dependencies on past decisions.
•Type Preservation — For greedy to work recursively, P' should be "the same kind of problem" as P. An activity selection problem should remain an activity selection problem; a knapsack should remain a knapsack.

Formal Definition:

Let P = (S, C, f) be an optimization problem where:

S = set of possible solutions
C = constraints that valid solutions must satisfy
f = objective function to optimize

After greedy choice x, the remaining problem P' = (S', C', f') where:

S' = solutions that extend {x} to complete solutions of P
C' = constraints from C, modified to account for x's inclusion
f' = objective measuring contribution beyond x's value

The greedy approach works when the optimal solution to P' combined with x yields an optimal solution to P.

When Type Preservation Fails

Some problems appear greedy-friendly but aren't because the remaining problem changes nature. In the 0/1 knapsack problem, after including an item, the remaining problem has modified capacity—but whether this changes the optimal strategy depends on the specific items remaining. This is why 0/1 knapsack requires dynamic programming: the remaining problem's optimal solution depends on which specific items we chose, not just their total weight.

Deep Dive: Activity Selection Remaining Problems

Let's trace through the activity selection problem in precise detail to see exactly how the remaining problem transforms at each step.

Initial Problem P₀:

Activities: A₁(1,4), A₂(3,5), A₃(0,6), A₄(5,7), A₅(3,9), A₆(5,9), A₇(6,10), A₈(8,11), A₉(8,12), A₁₀(2,14), A₁₁(12,16)
Format: Activity(start_time, finish_time)
Objective: Maximize number of non-overlapping activities
Constraints: Selected activities must not overlap

activity_selection_trace.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# Trace the remaining problem after each greedy choice
 
activities = [
    ("A1", 1, 4),   ("A2", 3, 5),   ("A3", 0, 6),
    ("A4", 5, 7),   ("A5", 3, 9),   ("A6", 5, 9),
    ("A7", 6, 10),  ("A8", 8, 11),  ("A9", 8, 12),
    ("A10", 2, 14), ("A11", 12, 16)
]
 
def analyze_remaining_problem(selected, activities, step):
    """Analyze the remaining problem after greedy choice."""
    print(f"
{'='*60}")
    print(f"STEP {step}: After selecting {selected}")
    print(f"{'='*60}")
    
    if selected:
        last_finish = max(a[2] for a in selected)
        remaining = [(name, s, f) for name, s, f in activities 
                    if (name, s, f) not in selected and s >= last_finish]
    else:
        remaining = activities[:]
    
    print(f"
Remaining Problem P_{step}:")
    print(f"  Number of activities: {len(remaining)} (was {len(activities)})")
    print(f"  Available activities: {[a[0] for a in remaining]}")
    
    if remaining:
        min_finish = min(a[2] for a in remaining)
        greedy_choice = [a for a in remaining if a[2] == min_finish][0]
        print(f"  Next greedy choice (earliest finish): {greedy_choice[0]} "
              f"(finish={greedy_choice[2]})")
        print(f"
  Constraint modification:")
        print(f"    Original: 'start_time >= 0'")
        print(f"    Modified: 'start_time >= {last_finish if selected else 0}'")
    
    return remaining
 
# Trace through the algorithm
selected = []
remaining = activities[:]
 
for step in range(4):  # First 4 steps
    remaining = analyze_remaining_problem(selected, activities, step)
    if remaining:
        # Make greedy choice
        min_finish = min(a[2] for a in remaining)
        choice = [a for a in remaining if a[2] == min_finish][0]
        selected.append(choice)

Problem Transformation at Each Step
Step	Choice Made	\|Remaining\|	Effective Constraint	Eliminated Activities
0 → 1	A₁ (finish=4)	11 → 3	start ≥ 4	A₂, A₃, A₅, A₆, A₇, A₁₀ (overlap with A₁)
1 → 2	A₄ (finish=7)	3 → 2	start ≥ 7	A₇ (overlaps with A₄)
2 → 3	A₈ (finish=11)	2 → 1	start ≥ 11	A₉ (overlaps with A₈)
3 → 4	A₁₁ (finish=16)	1 → 0	start ≥ 16	None remaining

Key Observations:

Monotonic constraint tightening: The "start ≥ t" constraint only increases, never decreases. This is crucial—it means we never need to reconsider previously eliminated activities.
Predictable problem reduction: Each step eliminates at least one activity (the chosen one), guaranteeing termination. But often many more are eliminated due to overlap.
State summarization: The entire history of choices is summarized by a single number: the latest finish time. We don't need to remember which activities we chose, only when our last commitment ends.
Type preservation: At every step, we're solving the same kind of problem: "maximize non-overlapping activities from those remaining." The problem nature never changes.

Mathematical Formalization of Problem Reduction

Let's formalize the remaining problem concept mathematically, which will help us reason precisely about greedy correctness.

Definition: Problem State

Define the state of a greedy optimization problem as a tuple σ = (R, C, v) where:

R = remaining elements that can be chosen
C = current constraints (may depend on previous choices)
v = value accumulated so far

Definition: State Transition Function

The greedy algorithm defines a transition function T: State × Element → State:

T(σ, x) = T((R, C, v), x) = (R', C', v')

where:

R' = R \ {x} \ {incompatible elements given x and C}
C' = constraints updated to reflect x's inclusion
v' = v + value(x)

The Markov Property of Greedy States

A well-designed greedy problem exhibits a Markov property: the optimal continuation from state σ depends only on σ, not on how we arrived at σ. This is analogous to the principle of optimality in dynamic programming. If this property fails—if the optimal future depends on the specific path taken—then greedy will likely fail.

Theorem: Greedy Optimality Condition

A greedy algorithm produces an optimal solution if and only if for every reachable state σ = (R, C, v):

Greedy Choice Existence: There exists some x* ∈ R such that x* is part of an optimal completion of σ (i.e., some optimal solution extending current choices includes x*).
Reducibility: T(σ, x*) results in a smaller problem that also satisfies condition 1.
Termination: Repeated application reaches a terminal state with R = ∅.

The Remaining Problem Perspective:

This theorem directly speaks to the remaining problem. After making choice x*, the remaining problem (R', C', 0) must itself have an optimal greedy solution. The value v' is "banked" and doesn't affect future decisions—only (R', C') matters.

This is why the remaining problem being "simpler" is so important: we need the inductive hypothesis (greedy works on smaller problems) to hold for the proof to go through.

greedy_state_machine.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Formal model of greedy state transitions
 
interface GreedyState<Element> {
    remaining: Set<Element>;        // R: available elements
    constraints: Constraint;        // C: current constraint state
    accumulated: number;            // v: value so far
}
 
interface Constraint {
    // Abstract constraint representation
    isSatisfied(element: any): boolean;
    afterChoice(element: any): Constraint;
}
 
class GreedyStateMachine<Element> {
    private selectionCriterion: (remaining: Set<Element>) => Element;
    private valueFunction: (element: Element) => number;
    private incompatibilityTest: (e: Element, chosen: Element, c: Constraint) => boolean;
    
    constructor(
        criterion: (remaining: Set<Element>) => Element,
        value: (element: Element) => number,
        incompatible: (e: Element, chosen: Element, c: Constraint) => boolean
    ) {
        this.selectionCriterion = criterion;
        this.valueFunction = value;
        this.incompatibilityTest = incompatible;
    }
    
    /**
     * The state transition function T(σ, x)
     * This is the formal model of "what remains after greedy choice"
     */
    transition(state: GreedyState<Element>, choice: Element): GreedyState<Element> {
        const newRemaining = new Set<Element>();
        
        for (const element of state.remaining) {
            // Element survives if:
            // 1. It's not the chosen element
            // 2. It's compatible with the choice under current constraints
            if (element !== choice && 
                !this.incompatibilityTest(element, choice, state.constraints)) {
                newRemaining.add(element);
            }
        }
        
        return {
            remaining: newRemaining,
            constraints: state.constraints.afterChoice(choice),
            accumulated: state.accumulated + this.valueFunction(choice),
        };
    }
    
    /**
     * Execute full greedy algorithm, returning all intermediate states
     */
    execute(initial: GreedyState<Element>): {
        states: GreedyState<Element>[];
        choices: Element[];
    } {
        const states: GreedyState<Element>[] = [initial];
        const choices: Element[] = [];
        let current = initial;
        
        while (current.remaining.size > 0) {
            const choice = this.selectionCriterion(current.remaining);
            choices.push(choice);
            current = this.transition(current, choice);
            states.push(current);
        }
        
        return { states, choices };
    }
}

Common Problem Reduction Patterns

Different classes of greedy problems exhibit characteristic patterns in how the remaining problem is structured. Recognizing these patterns helps identify when greedy approaches will work.

Pattern: Interval/Range Problems

In interval scheduling problems, the remaining problem is defined by a boundary shift:

Original Problem: Select from intervals in range [0, ∞)
After Choice of interval [a, b]: Select from intervals in range [b, ∞)

Key Properties:

The boundary only moves forward (monotonic)
The problem "shape" is identical—just with different boundary
State is fully characterized by a single number (boundary position)

Why This Works:

The earliest-finish-time heuristic works because:

Choosing earliest finish maximizes the remaining range [b, ∞)
A larger remaining range can only have more (or equal) options
Therefore, earliest-finish-time never "paints us into a corner"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def interval_reduction(intervals, current_time):
    """
    After choosing interval ending at current_time,
    the remaining problem is all intervals starting at/after current_time.
    
    This is a canonical 'boundary shift' reduction.
    """
    remaining = []
    for start, end in intervals:
        if start >= current_time:  # Shifted constraint
            remaining.append((start, end))
    
    # The remaining problem is IDENTICAL in form:
    # "Find maximum non-overlapping intervals from 'remaining'"
    # Only the input set has changed, not the problem type
    return remaining

When Remaining Problem Structure Fails

Understanding when greedy fails is as important as understanding when it succeeds. Failure often stems from pathological properties of the remaining problem.

Red Flags in Remaining Problem Structure

•Path-Dependent Optimality — If the optimal solution to the remaining problem depends on which specific elements were chosen (not just aggregate properties), greedy often fails. The 0/1 knapsack exhibits this: whether to include item j depends on which earlier items were included.
•Non-Monotonic Constraints — If constraints can loosen after a choice, earlier decisions may become suboptimal. Good greedy problems have constraints that only tighten (time boundaries advance, capacity decreases).
•Value Interaction — If the value of choosing x depends on other elements in the solution, greedy's local view misses global interactions. In clustering problems, an item's "value" depends on what cluster it joins.
•Reversibility Requirements — If optimal solutions require "undoing" or reconsidering earlier choices, greedy cannot succeed. Greedy commits irrevocably.
•Problem Type Mutation — If the remaining problem becomes a fundamentally different type of problem, the greedy heuristic may not apply. After some choices, the structure may shift from "maximization" to "satisfiability" or vice versa.

Case Study: Why Greedy Fails for 0/1 Knapsack

Consider: Capacity = 10, Items: [(weight=6, value=30), (weight=5, value=25), (weight=5, value=25)]

Greedy by value/weight ratio:

Item 1: ratio = 5, weight = 6 → Take it (remaining capacity: 4)
Items 2,3: ratio = 5, weight = 5 → Can't fit either!
Greedy solution: value = 30

Optimal solution:

Take items 2 and 3: weight = 10, value = 50

Why did greedy fail?

After choosing item 1, the remaining problem (capacity=4) has a different optimal structure than if we hadn't chosen it. The "remaining problem" after item 1 is: "can we fit anything in 4 units?" Answer: no. But the remaining problem after not choosing item 1 is: "fill 10 units optimally"—which has a good solution.

The critical flaw: the value of the remaining problem depends on which item we chose, not just how much capacity we used. With same capacity reduction (6 units) from a different item, outcomes differ.

The Fundamental Greedy Failure Mode

Greedy fails when early choices create remaining problems whose optimal solutions are not compatible with the globally optimal solution. In other words: greedy assumes that "optimal now + optimal remainder = global optimal." When this equation breaks—when optimal remainder depends on the PATH to the current state, not just the current state—greedy collapses.

Summary: Anatomy of the Remaining Problem

We've dissected the structure of what remains after a greedy choice. This understanding is foundational for reasoning about greedy correctness.

Key Takeaways

•Sequential Decomposition — Greedy algorithms decompose problems sequentially: make choice, transform problem, repeat. Each step creates a new "remaining problem."
•Five Dimensions — Analyze remaining problems along five dimensions: size reduction, constraint modification, objective preservation, independence, and type preservation.
•State Summarization — Well-behaved greedy problems have states that can be summarized compactly, independent of the path taken to reach them.
•Common Patterns — Remaining problem structures follow patterns: interval/boundary shift, capacity reduction, tree construction, and covering/requirement reduction.
•Failure Modes — Greedy fails when remaining problem optimality is path-dependent, constraints are non-monotonic, values interact, or reversibility is required.
•Markov Property — Successful greedy problems exhibit a Markov property: optimal continuation depends only on current state, not history.

Next Steps

You now understand what happens to a problem after a greedy choice. The next page explores why the remaining problem being 'similar but smaller' is so crucial—diving into the self-similar structure that makes greedy recursion possible.