Greedy Assignment Pass¶
A matching-and-allocation method — instantiates Greedy Stepwise Commitment
Seals the single highest-fit pairing available right now, decrements both sides' capacity, and never revisits it — one irreversible sweep through a matching problem.
Greedy Assignment Pass matches two sides of a problem — workers to tasks, reviewers to papers, slots to requests — by repeatedly sealing the single highest-fit pair available right now, decrementing the remaining capacity on both sides, and never revisiting a sealed pair. Its signature is the two-sided bookkeeping in one forward sweep: every commitment consumes a unit of the worker's capacity and a unit of the task's demand, shrinking the residual problem from both directions at once. Because the pass never backtracks, a pairing that looked best in isolation is locked in even if it later strands two other pairs that together would have scored higher.
Example¶
A conference has 600 submissions and 200 reviewers; each paper needs 3 reviews and each reviewer will take at most 9. A bidding phase produces a fit score for every reviewer–paper pair, blending expertise, keywords, and declared interest. A Greedy Assignment Pass ranks all feasible pairs by fit and seals them from the top. The strongest match — a security researcher and a paper squarely in her area, fit ≈0.94 — is committed first, dropping her remaining capacity to 8 and that paper's remaining need to 2.
It keeps sealing down the ranked list, skipping any pair whose reviewer is full or whose paper is already covered, until every paper has three reviews or no feasible pair remains. In minutes it produces a defensible assignment. The cost surfaces at the tail: a few mid-list papers end up with only lukewarm reviewers, because the specialists they needed were consumed earlier by marginally-better matches elsewhere — a strand the one-pass rule cannot undo.
How it works¶
- Score the feasible pairs on two-sided fit.
- Seal the top pair — commit the highest-scoring pair whose two sides both still have capacity.
- Decrement both sides and drop any party now exhausted from further consideration.
- Repeat down the ranked candidates until demand is met or nothing feasible remains.
What distinguishes it: the residual state is two-sided, and the sweep is single — no augmenting paths, no re-matching of a pair once sealed.
Tuning parameters¶
- Selection scope — re-rank all pairs globally after each seal (best quality), take a single sorted sweep (fastest), or go row-by-row. Trades runtime against how often the greedy pick is genuinely the best available.
- Capacity granularity — one-to-one, or many-to-many with per-side quotas; sets how the residual trackers decrement.
- Fit threshold — a floor below which a pair is left unmatched rather than forced, trading coverage against quality.
- Tie-break — among equal fits, prefer the party with the scarcest remaining options — a mild look-ahead that reduces stranding.
- Swap budget — zero for a pure greedy pass, or a small allowance to undo a seal that later blocks two better pairs — a step toward the exact solution.
When it helps, and when it misleads¶
Its strength is that it is near-instant and easy to justify pair-by-pair, and it is strong when fit scores are lopsided so the best pairing is rarely contested. It also degrades gracefully to a sensible partial assignment when supply runs short.
Greedy matching can be arbitrarily worse than the optimal assignment — grabbing one locally excellent pair can block two merely-good pairs worth more together — and when an exact method is affordable that shortfall is pure waste. The optimum here is a solved, polynomial computation (the Hungarian / Kuhn–Munkres algorithm)[n1], so greedy is a deliberate trade of quality for speed, not a necessity. It is also easy to run to justify a roster already decided, by tuning the fit score after the fact. The discipline is to benchmark the greedy result against the optimal — or a swap-improved — assignment on sample instances before trusting it at scale.
How it implements the components¶
residual_capacity_tracker— the remaining capacity of every worker and the remaining demand of every task, decremented on each seal; the state that drives the pass.local_priority_score— the fit score on each candidate pair that the pass ranks by.selection_and_tie_break_rule— take the top-scoring feasible pair, breaking ties toward the scarcest side.
It does not model an irreversible time-ordered dispatch against deadlines (Earliest-Deadline-First Dispatch), carry a solution-quality guarantee or benchmark (Greedy Set-Cover Heuristic), or enforce a structural invariant / matroid (Kruskal-Style Edge Acceptance).
Related¶
- Instantiates: Greedy Stepwise Commitment — a single non-backtracking sweep that consumes capacity as it commits.
- Sibling mechanisms: Highest-Marginal-Gain-First Rule · Greedy Set-Cover Heuristic · Sorted Candidate Sweep · Priority-Queue Step Selection · Lexicographic Priority Rule
Editorial Notes¶
Form Classification¶
Form family: Decision, Gate & Allocation
Rationale: Greedy Assignment Pass operates as a case-specific gate, selection, routing, prioritization, or resource disposition because it seals the single highest-fit pairing available right now, decrements both sides' capacity, and never revisits it — one irreversible sweep through a matching problem.
Independent corroboration: The frozen evidence defines Greedy Assignment Pass as 'Seals the single highest-fit pairing available right now, decrements both sides' capacity, and never revisits it — one irreversible sweep through a matching problem', so its operative form is Decision, Gate & Allocation.
Nearest alternative: Analysis, Modeling & Optimization — Pair scores are consumed, but the mechanism's defining act is irrevocably allocating capacities by sealing matches.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Operations Research
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Universal
Rationale: Assignment and matching optimization supply the greedy-versus-global-optimum contrast.
Related originating lineages:
- Computer Science & Software Engineering — Algorithm design formalizes irreversible greedy choice and its complexity tradeoff.
- Mathematics — Bipartite matching provides the formal structure and optimum comparator.
Review resolution: Both reviewers agree that operations_research is primary: Assignment and matching optimization supply the greedy-versus-global-optimum contrast. I retain computer_science, mathematics only as formative lineage, not as a list of later applications. I resolve origin_mode as cross_disciplinary_synthesis because the artifact joins distinct disciplinary contributions. I resolve domain_reach as universal because it is broadly applicable across essentially all domains. Encyclopedia synthesis is false because the exact generalized packaging is already established enough that encyclopedia-specific synthesis is not required.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
The single-pass, no-rematch rule is the whole distinction from an optimal matcher. The moment you allow sealed pairs to be undone via augmenting paths, you are no longer running a greedy pass but converging on the exact assignment — a different mechanism with a different cost profile.
[n1] The assignment problem — a minimum-cost perfect matching on a bipartite graph — is solved exactly in polynomial time by the Hungarian (Kuhn–Munkres) algorithm. Greedy assignment trades that guaranteed optimum for speed and simplicity. ↩