A greedy algorithm commits to the best local choice. See why largest-first chunking can lose, and what a problem-specific optimality proof must establish.
Greedy algorithm
A greedy algorithm builds a solution by repeatedly choosing the best available next step under a local rule and committing to that choice. It does not revisit earlier choices to compare complete alternatives. In quant work, that distinction matters whenever a fast allocation or scheduling rule is presented as an optimizer: a sensible next step can still lead to a worse final result. Greedy methods are globally optimal for some problems, while other uses are heuristics. NIST's definition makes that distinction explicit.
A feasible choice can close off the optimum
Consider a fictional chunking problem. Available chunk sizes are 1, 3 and 4 units, each reusable without limit. The target is exactly 6 units, and the objective is to use the fewest chunks. There are no fees, time effects or other constraints.
The local rule is “take the largest chunk no bigger than the remaining quantity.” It chooses 4, leaving 2. Neither 4 nor 3 now fits, so it takes 1 and then 1: three chunks. But 3 + 3 reaches the target with two chunks.
Two is the global minimum: one chunk cannot reach 6 because the largest available size is 4, and a two-chunk solution exists. Once the rule commits to 4, it cannot reach that optimum without undoing its first choice. Local feasibility has preserved the ability to finish, but not the ability to finish optimally.
Fictional chunks of sizes 1, 3 and 4 must total exactly 6 units. Largest-first chooses 4, then 1, then 1: three chunks. The optimum chooses 3 then 3: two chunks. Both rows cover the same six units.
The largest immediate reduction in the remaining quantity does not minimize the final chunk count. Chunk sizes are reusable; this is a fictional integer allocation problem.
This counterexample rejects the claim that largest-first is always optimal for arbitrary chunk sizes. It does not reject every greedy algorithm. The chunks are a teaching device, not an optimal-execution recommendation: real order execution introduces liquidity, market impact, timing and risk objectives that this model omits.
Implement the rule; test the claim separately
Here is the complete largest-first rule for these fixed sizes. Its input contract is a nonnegative integer target. The size-1 chunk ensures every such target can be reached.
deflargest_first(target: int) -> list[int]:"""Build a feasible chunk list for a nonnegative integer target.""" sizes = (1, 3, 4)
chosen = []
remaining = target
while remaining > 0:
chunk = max(size for size in sizes if size <= remaining)
chosen.append(chunk)
remaining -= chunk
return chosen
chosen = largest_first(6)
print(chosen, len(chosen), sum(chosen))
# [4, 1, 1] 3 6print(largest_first(0))
# []
The loop deliberately shows each commitment. max selects the largest feasible size; it does not search for the smallest final chunk count. The output confirms feasibility, not optimality. For a small instance, brute-force search over all chunk-count combinations supplies an independent benchmark. Dynamic programming can instead compare choices while reusing solutions to smaller remaining targets.
What makes a greedy rule safe?
An optimality claim needs a structural argument connecting the local rule to the full objective. An exchange argument often starts with an optimal solution and shows that its first decision can be replaced by the greedy decision without worsening the objective or breaking feasibility. One then proves that solving the remaining subproblem the same way completes an optimal solution. Other problems use a cut property or a different invariant; “it looks best now” is not that proof.
For example, to maximize the number of non-overlapping jobs on one resource, select the compatible job that finishes earliest. In an optimal schedule, replacing its first job with the earliest-finishing job leaves at least as much room for later jobs. Repeating on the remainder proves the rule safe. If jobs instead carry different rewards and the objective becomes maximum total reward, that exchange need not preserve the objective. MIT's interval-scheduling notes develop precisely this boundary.
For a proposed quant heuristic, write down the objective, feasible actions and local ranking rule first. Then identify the proof and its assumptions—or measure the heuristic against an independent optimum on tractable cases. Changing constraints or the objective can invalidate a formerly correct greedy rule.
