Sorted Candidate Sweep¶
One-pass greedy method — instantiates Greedy Stepwise Commitment
Scores and sorts every candidate once, then makes a single pass accepting each in order whenever it keeps the solution feasible — no re-scoring, no revisiting.
Sorted Candidate Sweep is greedy stripped to its leanest form: score all candidates up front, sort them once, then sweep down the list accepting each one whenever adding it keeps the solution feasible, and skipping it otherwise. The one idea that makes it this mechanism is that the scores are frozen — computed before the sweep begins and never revised as commitments accumulate. That single static sort is what separates it from a live priority queue, and it is why the method is fast, simple, and correct only under a specific structural condition.
Example¶
A basketball team enters a draft with a fixed number of roster slots per position. It ranks every available player by a single value score, then sweeps down that ranked list once: for each player, it drafts them if a slot at their position is still open, and skips them otherwise. The best center goes early; a later, lower-ranked guard is still taken if the guard slots aren't yet full; a superb player at an already-filled position is passed over.
Because the "one slot cap per position" constraint makes the set of legally draftable rosters a partition matroid, this single frozen-order sweep provably yields the maximum-value feasible roster — no back-and-forth, no re-ranking after each pick. The only per-player decision the method ever makes is the feasibility check: is there still room?
How it works¶
- Compute the local priority score for every candidate and sort the whole field once, up front.
- Sweep through the sorted list a single time. For each candidate, accept it if the solution stays feasible after adding it; otherwise skip it permanently.
- Never recompute a score and never revisit a skipped candidate. What distinguishes it from Priority-Queue Step Selection is exactly this staticness: there is no decrease-key, no re-prioritization — the initial sort order is the commitment order.
Tuning parameters¶
- Sort key and direction — the frozen score and whether higher or lower comes first; this ordering is the entire strategy, since nothing after it adapts.
- Feasibility oracle — how strict and how expensive the "still feasible?" test is; it is the method's only per-step logic, so its cost dominates after the sort.
- Tie-break within equal scores — how candidates with identical scores are ordered, which can change the accepted set when the structure is not a clean matroid.
- Post-sweep repair — whether a light improvement pass is allowed afterward, bridging toward Trap-Sentinel Escalation when the structure isn't matroid-clean.
When it helps, and when it misleads¶
Its strength is extreme economy: one sort dominates the cost, the sweep is a single linear pass, and when the feasible sets form a matroid the frozen-order sweep is not just fast but exactly optimal.[n1]
Its failure mode is that the optimality is entirely borrowed from that structure. Off a matroid — 0/1 knapsack sorted by value or value-density is the standard example — the one-pass sweep can be arbitrarily far from best, because a greedy early accept can foreclose a far better combination the frozen scores never anticipated. And since the scores never update, the method is blind to how each acceptance changes the real worth of later candidates. The classic misuse is to run the sweep on a non-matroid problem and present its output as optimal. The discipline is to verify the matroid or exchange property first; where it does not hold, treat the sweep as a heuristic to be repaired rather than trusted.
How it implements the components¶
local_priority_score— the score by which candidates are sorted once, up front, and never recomputed; the static-score signature that defines the method.constraint_and_invariant_guard— the sole per-step decision: accept a candidate only if the feasibility invariant survives (a roster slot remains, no cycle forms, capacity holds).exchange_property_or_matroid_check— the certificate that a single sorted pass is optimal: it holds exactly when the feasible sets satisfy the matroid exchange property.
It does not re-prioritize or track the residual live — that reactive engine is Priority-Queue Step Selection — nor generate endpoint-relative candidates (Nearest-Neighbor Route Extension); repairing a sweep run on non-matroid structure is Trap-Sentinel Escalation.
Related¶
- Instantiates: Greedy Stepwise Commitment — the static, sort-once form of greedy commitment.
- Sibling mechanisms: Priority-Queue Step Selection · Kruskal-Style Edge Acceptance · Lexicographic Priority Rule · Nearest-Neighbor Route Extension · Shortest-Processing-Time-First Rule · Trap-Sentinel Escalation · Highest-Marginal-Gain-First Rule · Greedy Set-Cover Heuristic · Greedy Assignment Pass · Earliest-Deadline-First Dispatch · Dijkstra-Style Frontier Expansion
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Sorted Candidate Sweep operates as an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution because it scores and sorts every candidate once, then makes a single pass accepting each in order whenever it keeps the solution feasible — no re-scoring, no revisiting.
Independent corroboration: The frozen evidence defines Sorted Candidate Sweep as 'Scores and sorts every candidate once, then makes a single pass accepting each in order whenever it keeps the solution feasible — no re-scoring, no revisiting', so its operative form is Analysis, Modeling & Optimization.
Nearest alternative: Decision, Gate & Allocation — Sorted Candidate Sweep includes features of a case-specific gate, selection, routing, prioritization, or resource disposition, but its defining operation is an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Operations Research
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Sorting candidates once and greedily accepting feasible items is a classical greedy optimization algorithm.
Related originating lineages:
- Computer Science & Software Engineering — Algorithm design analyzes sorting cost and one-pass implementation.
- Mathematics — Matroid and approximation theory characterize when greedy selection is optimal or bounded.
Review outcome: Independent reviewer agreement; high confidence.
Notes¶
Because it scores once and never updates, the sweep cannot react to how early accepts reshape the problem — the very reactivity that Priority-Queue Step Selection exists to add. The two are the static and dynamic poles of the same idea: use the sweep when the scores genuinely don't change under commitment (and ideally when the structure is a matroid), and the queue when they do.
[n1] A greedy sort-and-accept sweep returns an optimal solution exactly when the feasible sets form a matroid — the classical matroid characterization of greedy optimality (Rado–Edmonds). Kruskal's minimum-spanning-tree algorithm is the graphic-matroid instance of this same sweep. ↩