Chapter 7. 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 four greedy algorithms in this chapter 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 parallelises 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-IntervalPartition. $G[j] \geq 1$ is the room assigned to course $j$. Forbidden when $j$ is unfixed but every overlapping earlier course is fixed. Advance: $G[j]$ to the least free room and mark $j$ fixed.
• LLP-MinMaxLateness. $G[j]$ is the start time of job $j$ (jobs are pre-sorted by deadline). Forbidden when $G[j] < \sum_{i < j} t[i]$. Advance: raise $G[j]$ to that 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. The forbidden predicate is $\neg G[j] \wedge (\forall i < j : \neg G[i] \vee f[i] \leq s[j])$ — index $j$ is unselected and is compatible with every already-selected earlier interval. The advance rule sets $G[j] := \text{true}$. 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-IntervalPartition

Each course $j$ is assigned a positive integer room $G[j]$, with overlapping courses getting distinct rooms. $\textit{pre}[j]$ is the set of earlier courses that overlap with $j$. Index $j$ is forbidden when every $i \in \textit{pre}[j]$ is fixed but $j$ is not; advancing assigns $G[j]$ to the least free room not used by any predecessor and marks $j$ fixed. The minimum number of rooms equals the maximum overlap depth.

Time complexity: $O(n \log n)$ via a min-heap of room finish times.

LLP-MinMaxLateness

Jobs are pre-sorted by deadline. $G[j]$ is the start time of job $j$ (initially $0$). $j$ is forbidden when $G[j] < \sum_{i < j} t[i]$; the advance lifts $G[j]$ to that prefix sum. 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)$, where $n$ is the number of items.

Constrained greedy

Several practical greedy problems carry side constraints: certain intervals are mandatory, certain rooms are excluded for certain courses, jobs have release times, or jobs have precedences. Each such constraint is itself a one-rule LLP program operating on the same state vector $G$ as the base greedy. The Lattice-Linear Language's predicate-conjunction operator $\&\&$ composes them with the base program; the composed predicate is still lattice-linear because lattice-linearity is closed under conjunction.

Mandatory intervals

A subset $S \subseteq [n]$ of intervals must appear in the selected set. Forbidden when $j \in S$ but $G[j] = \text{false}$; the advance sets $G[j] := \text{true}$ unless $j$ overlaps another already-selected interval, in which case the program halts ``infeasible''. Composed with LLP-IntervalScheduling: $[\,\textsf{LLP-IntervalScheduling}\,\&\&\,\textsf{Mandatory}\,]$.

Time complexity: $O(n)$ extra work on top of LLP-IntervalScheduling.

boolean[] MandatoryIntervals(int[] s, int[] f, boolean[] S) {
  boolean[] G = false;
  forbidden (j) : S[j] && !G[j] =>
    advance : {
      if (exists k : G[k] && overlap(j, k, s, f)) return null;
      G[j] = true;
    };
  return G;
}

Excluded rooms

For each course $j$, a set $R_j$ of rooms is unsuitable. Forbidden when $G[j] \in R_j$; the advance picks the smallest room $r \notin R_j$ that no overlapping earlier course is using. Composed with LLP-IntervalPartition: $[\,\textsf{LLP-IntervalPartition}\,\&\&\,\textsf{ExcludedRooms}\,]$.

Time complexity: $O(n)$ extra per advance, $O(n^2)$ aggregate worst case.

int[] ExcludedRooms(set<int>[] R, set<int>[] pre, int[] G) {
  forbidden (j) : G[j] in R[j] =>
    advance :
      G[j] = min r in [1..n] :
        !(r in R[j]) &&
        forall k in pre[j] : G[k] != r;
  return G;
}

Release times

Each job $j$ has a release time $r_j$ before which it cannot start. Forbidden when $G[j] < r_j$; the advance lifts $G[j]$ to $r_j$. Composed with LLP-MinMaxLateness: $[\,\textsf{LLP-MinMaxLateness}\,\&\&\,\textsf{ReleaseTimes}\,]$.

Time complexity: $O(n)$ extra work.

int[] ReleaseTimes(int[] r, int[] G) {
  forbidden (j) : G[j] < r[j] =>
    advance : G[j] = r[j];
  return G;
}

Precedences

Each job $j$ has a set $\textit{pre}(j)$ of jobs that must finish before $j$ can start. Forbidden when some $i \in \textit{pre}(j)$ has not finished by $G[j]$; the advance raises $G[j]$ to the latest finish time of its predecessors. Composed with LLP-MinMaxLateness: $[\,\textsf{LLP-MinMaxLateness}\,\&\&\,\textsf{Precedences}\,]$. Infeasibility manifests as a cycle in the precedence relation.

Time complexity: $O(|\textit{pre}|)$ extra work, where $|\textit{pre}| = \sum_j |\textit{pre}(j)|$.

int[] Precedences(set<int>[] pre, int[] t, int[] G) {
  forbidden (j) : exists i in pre[j] : G[j] < G[i] + t[i] =>
    advance : G[j] = max i in pre[j] : G[i] + t[i];
  return G;
}

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 8 (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.