Unit 3: Greedy Method

I. Orientation — The Greedy Design Principle

A greedy algorithm constructs a solution incrementally, choosing at each stage the locally best available option. It does not reconsider earlier choices; therefore, it produces an optimal solution only when the problem has suitable structural properties.

A. Defining Characteristics

This orientation establishes the assumptions and terminology used throughout the unit.

• Local choice: At step (i), the algorithm selects the candidate that maximizes or minimizes a stated criterion, such as profit, edge weight, or tentative distance.
• Irrevocability: Once a choice is accepted, it is normally not undone. Prim’s algorithm, for example, permanently adds a minimum-weight crossing edge.
• Feasibility: Every accepted choice must preserve the problem’s constraints; Kruskal’s algorithm rejects an edge if it creates a cycle.
• Greedy-choice property: Some globally optimal solution must begin with a locally optimal choice.
• Optimal substructure: After the first choice, the remaining decisions must form an optimal solution to the resulting subproblem.
• Efficiency: Greedy algorithms often use sorting, priority queues, or disjoint-set structures and commonly run in (O(n\log n)) time.
• Proof requirement: A plausible local rule is not sufficient. Correctness is usually established through an exchange argument, a cut property, or induction.

II. General Method — Constructing Greedy Algorithms

A. General method

The general method repeatedly selects the best feasible candidate until a complete solution is formed.

• Candidate set: Contains the objects from which a solution is built, such as items, graph edges, or vertices.
• Selection function: Identifies the locally best candidate according to the greedy rule.
• Feasibility function: Determines whether adding a candidate violates a constraint.
• Objective function: Measures solution quality, such as total profit or total edge weight.
• Solution function: Determines when the constructed set constitutes a complete answer.
• Generic structure:

GREEDY(C):
    S ← ∅
    while not SOLUTION(S) and C ≠ ∅:
        x ← SELECT(C)
        C ← C − {x}
        if FEASIBLE(S ∪ {x}):
            S ← S ∪ {x}
    return S

Here, (C) is the candidate set, (S) is the partial solution, and (x) is the currently selected candidate.

• Correctness pattern:
  • Show that the first greedy choice can belong to an optimal solution.
  • Reduce the remaining problem to a smaller instance of the same form.
  • Apply induction to conclude that all choices together are optimal.
• Exchange argument: If an optimal solution uses a different first choice, replace it with the greedy choice without worsening the objective value.

B. Applications and Limitations

The method is powerful when local decisions align with global optimality, but it does not solve every optimization problem.

• Suitable problems: Fractional knapsack, minimum spanning trees, activity selection, Huffman coding, and Dijkstra’s shortest-path problem.
• Failure condition: Greedy selection may discard combinations whose delayed benefit is greater.
• Diagnostic principle: A counterexample to the proposed selection rule disproves it; successful examples do not establish correctness.
• Resource use: Sorting usually contributes (O(n\log n)), while priority queues support repeated minimum extraction efficiently.

III. Knapsack Problem — Maximizing Value under Capacity

A. Knapsack problem

The knapsack problem selects objects of weight (w_i) and profit (p_i) for a knapsack of capacity (M), maximizing total profit without exceeding that capacity.

Maximize   Σ(pᵢxᵢ)
subject to Σ(wᵢxᵢ) ≤ M

Here, (x_i) is the amount of item (i) selected. In fractional knapsack, (0\leq x_i\leq1); in 0/1 knapsack, (x_i\in{0,1}).

1. Fractional knapsack
   • Greedy criterion: Sort items by non-increasing profit density (r_i=p_i/w_i).
   • Selection: Take each item completely while capacity permits, then take the needed fraction of the next item.
   • Correctness: Replacing lower-density weight with equal higher-density weight cannot reduce profit, establishing the exchange property.
   • Complexity: Sorting costs (O(n\log n)); the selection scan costs (O(n)).

FRACTIONAL-KNAPSACK(items, M):
    sort items by decreasing pᵢ/wᵢ
    profit ← 0
    for each item i:
        xᵢ ← min(1, M/wᵢ)
        profit ← profit + pᵢxᵢ
        M ← M − wᵢxᵢ
        if M = 0: break
    return profit

2. 0/1 knapsack
   • Restriction: An item must be taken completely or rejected.
   • Greedy failure: Profit density alone is not reliable because item combinations matter.
   • Contrast: Fractional divisibility supports exchanges; indivisibility destroys that argument.
   • Alternative: Dynamic programming solves the integer-capacity version in (O(nM)) time.

• Worked example: For items ((p,w)=(60,10),(100,20),(120,30)) and (M=50), densities are (6,5,4). Taking the first two items and (20/30) of the third yields (60+100+80=240). Under 0/1 rules, the best feasible total is (100+120=220).

B. Applications and Limitations

Knapsack modeling applies when a limited resource must be assigned to opportunities of unequal returns.

• Applications: Divisible resource allocation, cargo loading, bandwidth allocation, and investment distribution.
• Assumption: Fractional knapsack requires profit and weight to vary proportionally when an item is divided.
• Limitation: Dependencies, indivisible items, multiple constraints, or nonlinear values generally require dynamic programming or other optimization methods.

IV. Minimal Spanning Trees: Prim's Algorithm — Growing One Tree

A. Minimal spanning trees: Prim's algorithm

Prim’s algorithm finds a minimum spanning tree (MST) of a connected, undirected, weighted graph by repeatedly attaching the cheapest vertex outside the current tree.

• Spanning tree: For a graph (G=(V,E)), it connects all (|V|) vertices using exactly (|V|-1) edges and contains no cycle.
• Objective: Minimize

w(T) = Σ w(e), for every edge e ∈ T

Here, (T) is a spanning tree and (w(e)) is the weight of edge (e).

• Greedy choice: Select the minimum-weight edge crossing from vertices already in the tree to vertices outside it.
• Cut property: A lightest edge crossing any cut is safe for inclusion in some MST.
• Priority-queue form:

PRIM(G, root):
    key[root] ← 0; key[v] ← ∞ for all other v
    parent[v] ← NIL
    place all vertices in a min-priority queue Q
    while Q ≠ ∅:
        u ← EXTRACT-MIN(Q)
        for each edge (u,v) with v in Q:
            if w(u,v) < key[v]:
                parent[v] ← u
                key[v] ← w(u,v)
                DECREASE-KEY(Q, v)

Here, key[v] is the cheapest known edge connecting (v) to the tree, and parent[v] records that edge.

• Complexity: An adjacency list with a binary heap gives (O(E\log V)); an adjacency matrix gives (O(V^2)).

B. Applications and Limitations

Prim’s algorithm is particularly effective for dense graphs or when adjacency-based growth is natural.

• Applications: Network cabling, electrical grids, road planning, and clustering.
• Disconnected input: It spans only the root’s component unless restarted, producing a minimum spanning forest.
• Negative weights: They are permitted because MST correctness does not depend on nonnegative weights.
• Tie handling: Equal-weight choices may produce different MSTs with the same minimum total weight.

V. Minimal Spanning Trees: Kruskal's Algorithm — Merging Components

A. Minimal spanning trees: Kruskal's algorithm

Kruskal’s algorithm forms an MST by considering all edges globally in non-decreasing weight order and adding an edge only when it joins two different components.

• Greedy choice: Select the cheapest remaining edge that does not create a cycle.
• Forest invariant: Accepted edges always form a collection of disjoint trees.
• Cycle test: A disjoint-set union structure maintains components through FIND and UNION.

KRUSKAL(G):
    T ← ∅
    MAKE-SET(v) for every vertex v
    sort all edges by non-decreasing weight
    for each edge (u,v) in sorted order:
        if FIND(u) ≠ FIND(v):
            T ← T ∪ {(u,v)}
            UNION(u,v)
        if |T| = |V| − 1: break
    return T

Here, (T) is the accepted edge set. FIND(v) identifies the component containing (v), while UNION merges two components.

• Correctness: The chosen edge is a lightest edge crossing the cut between two current components, so the cut property makes it safe.
• Complexity: Edge sorting costs (O(E\log E)). Union by rank and path compression make disjoint-set operations nearly constant amortized time.
• Prim comparison: Prim grows one connected tree from a root; Kruskal grows many trees and merges them.

B. Applications and Limitations

Kruskal’s algorithm is especially convenient for sparse graphs represented as edge lists.

• Applications: Sparse network design, image segmentation, clustering, and approximate solutions based on MST structure.
• Disconnected graph: It naturally returns a minimum spanning forest.
• Parallel edges: They are valid; the cheaper safe edge is considered first.
• Limitation: Sorting all edges may be less attractive for very dense graphs than an (O(V^2)) implementation of Prim’s algorithm.

VI. Single-Source Shortest Paths — Dijkstra’s Greedy Algorithm

A. Single-source shortest paths

The single-source shortest-path problem computes the minimum distance from one source vertex (s) to every reachable vertex; Dijkstra’s greedy algorithm is correct when all edge weights are nonnegative.

• Path distance: For path (P),

w(P) = Σ w(e), for every edge e on P
δ(s,v) = minimum w(P) over all paths from s to v

Here, (w(P)) is path weight and (\delta(s,v)) is the true shortest distance from (s) to (v).

• Relaxation: For edge ((u,v)), replace (d[v]) with (d[u]+w(u,v)) when that value is smaller.
• Greedy choice: Permanently settle the unsettled vertex having the smallest tentative distance.
• Correctness condition: Nonnegative edges ensure that no later path through a farther unsettled vertex can improve a settled distance.

DIJKSTRA(G, s):
    d[s] ← 0; d[v] ← ∞ for v ≠ s
    parent[v] ← NIL
    insert all vertices into min-priority queue Q
    while Q ≠ ∅:
        u ← EXTRACT-MIN(Q)
        for each edge (u,v):
            if d[v] > d[u] + w(u,v):
                d[v] ← d[u] + w(u,v)
                parent[v] ← u
                DECREASE-KEY(Q, v)

• Output: Array (d) stores shortest distances; following parent links reconstructs a shortest-path tree.
• Complexity: A binary heap gives (O((V+E)\log V)), commonly written (O(E\log V)) for connected graphs; an adjacency matrix gives (O(V^2)).

B. Applications and Limitations

Single-source shortest paths support routing and minimum-cost movement from a fixed origin.

• Applications: Navigation, packet routing, game maps, robot motion, and dependency-cost analysis.
• Unreachable vertices: Their distances remain (\infty).
• Negative edges: Dijkstra’s algorithm may settle a vertex prematurely; Bellman–Ford is appropriate when negative edges exist.
• Negative cycles: If reachable from the source, they make shortest distances undefined because repeated traversal decreases path cost without bound.