Chapter 6. Greedy Algorithms

Each greedy algorithm in this chapter has a lattice-linear formulation: a state vector $G$, a forbidden predicate that detects local violations of the greedy invariant, and an advance rule that fixes them.

This page: LLP forms. View classical forms »

The LLP perspective

The greedy algorithms on this page all admit lattice-linear reformulations on a state vector $G$. In each case the predicate $B$ pins down a unique target vector $G^\star$, the forbidden condition is $G[j] \prec G^\star[j]$ for the chapter's local order, and the advance step raises $G[j]$ to $G^\star[j]$. Several of the targets are prefix-structured, so the LLP advance step parallelizes directly via a parallel prefix scan: all forbidden indices read their targets from the same scan output and advance concurrently in a single logical round.

• LLP-IntervalScheduling. $G[j] \in \{\text{false}, \text{true}\}$ marks selected intervals. Forbidden when $G[j]$ is unselected and compatible with every already-selected earlier interval. Advance: $G[j] := \text{true}$.
• LLP-MinMaxLateness. $G[j]$ is the start time of job $j$ (jobs are pre-sorted by deadline). Written with ensure: $G[j] \geq \sum_{i < j} t[i]$, which forbids $j$ while $G[j]$ is below that prefix sum and advances it to the prefix sum.
• LLP-FractionalKnapsack. $G[j] \in [0, 1]$ is the fraction of item $j$ taken (items pre-sorted by $v/w$ density). Forbidden when $G[j] < G^\star[j]$. Advance: $G[j] := G^\star[j]$.

LLP-IntervalScheduling

$G[j] = \text{true}$ marks selected intervals. Jobs sorted by finish time are held in a doubly linked list via $prev[\cdot]/next[\cdot]$; job $0$ starts selected. Index $j$ is forbidden when it is neither selected nor deleted and either (a) its current list-predecessor already finished by $s[j]$ — advance selects it, $G[j] := \text{true}$ — or (b) its predecessor is selected but still overlaps $j$ — advance deletes $j$ from the list in $O(1)$ via $next[prev[j]] := next[j];\ prev[next[j]] := prev[j]$. Sweeping $j$ in order of finish time matches the classical earliest-finish-time greedy.

Time complexity: $O(n)$ once intervals are sorted by finish time, $O(n \log n)$ overall, where $n$ is the number of intervals.

LLP-MinMaxLateness

Jobs are pre-sorted by deadline. $G[j]$ is the start time of job $j$ (initially $0$). The program states the constraint as ensure $G[j] \geq \sum_{i < j} t[i]$, shorthand for forbidding $j$ while $G[j]$ is below that prefix sum and lifting $G[j]$ to it. After convergence, $\textit{lateness} = \max_j \max(0, G[j] + t[j] - d[j])$. Because every target is a prefix sum, all forbidden indices advance in a single logical round.

Time complexity: $O(n \log n)$ for the sort, $O(n)$ for the schedule, where $n$ is the number of jobs.

LLP-FractionalKnapsack

Items are pre-sorted by value-density $v/w$ in non-increasing order. Let $S_j = \sum_{k \leq j} w[k]$ be the cumulative weight. The target is $G^\star[j] = 1$ while $S_j \leq W$, the partial fraction at the breakpoint, and $0$ once $S_{j-1} \geq W$. Forbidden when $G[j] < G^\star[j]$; advance raises $G[j]$ to that value. All forbidden indices advance in a single logical round, driven by a prefix-sum scan over $w$.

Time complexity: $O(n \log n)$ for the sort, then $O(n)$: one left-to-right scan fills $S$, and each target $G^\star[j]$ is read from $S[j-1], S[j]$ in $O(1)$.

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.

Looking ahead

The interval-scheduling and min-max-lateness ideas reappear in Chapter 7 (Shortest Paths) as the engine behind Dijkstra's algorithm: Dijkstra's "fix the closest unfixed vertex next" is exactly the greedy choice on the SSSP lattice. The exchange-argument template extends naturally to LLP correctness proofs.