Complete greedy number partitioning
Algorithms AIMech:CompleteGreedyNumberPartitioning DRAFT
Aliases: CGA, Complete greedy algorithm for number partitioning
A complete anytime number-partitioning search that assigns weights in decreasing order to a fixed number of bins, explores the currently lightest-bin choices first, and retains the smallest load range while pruning by valid bounds and bin symmetry.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 589 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 63, 0, 0 lines. All distinct match contents were inspected. Semantic matching covered 67 AIO and 96 native definitions, with every matched definition read. 6 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. The named CGA performs complete item-to-bin assignment with a greedy successor order. It is distinct from generic DFS, discrepancy ordering and KK/CKK residual composition. Its two-way and multiway forms share this item-assignment mechanism and are retained in one range-minimization record; k-way bounds are not asserted to be attainable. Existing hits are neighboring records, rendered text and discovery leads. No suitable pinned AIO counterpart was identified.
Claims & Grounded Evidence
6 Claims
Mechanism
#greedy-first-assignment
Sort a finite nonempty multiset of nonnegative weights in decreasing order. Search assignments of each next weight to k interchangeable bins, with k>=2, visiting bins in increasing current-load order. The first complete preferred path is sorted greedy partitioning. Keep the best complete assignment found under the range objective max(loads)-min(loads). This assigns original items one at a time, unlike KK or CKK composition of residual subpartitions.
Mechanism
#symmetry-scope
For the unconstrained objective, bins with equal current loads give equivalent remaining load-search problems, so only one such choice needs exploration at that node. This includes the initial empty-bin symmetry. It preserves the best objective value but need not enumerate every distinct item-membership partition. Extra bin-specific restrictions or cardinality constraints require a new symmetry argument; equality of loads alone would not justify ignoring them.
Mechanism
#optimistic-range-bound
Let smax be the largest current bin load and R the sum of unassigned nonnegative weights. A lower bound on final range is max(0, smax-(sum(other current loads)+R)/(k-1)). If it is at least the best complete range, the subtree cannot improve that incumbent. For k>2 the average in this bound need not be attainable with indivisible weights. With current loads (10,0,0) and remaining item 4, the bound is 8 but the minimum attainable range is 10. In the special two-way case, a current load difference at least R is solved by placing all remaining items in the lighter bin.
Limitation
#complete-versus-interrupted
On a finite instance, exhaustive search with sound pruning can certify an optimum, but a limited run can return only its feasible incumbent. Exact integer loads have theoretical minimum range 0 when the total is divisible by k and otherwise at least 1; attaining the applicable lower bound permits immediate certification, but divisibility does not ensure it is attainable. The search is exponential in the worst case. In a constructed two-way example with weights 8,7,6,5,4, the greedy range is 4, a one-node run remains uncertified at 4, and complete search reaches 0.
Limitation
#range-is-not-makespan
The multiway formulation curated here minimizes load range. For k>=3 this does not ensure that the returned solution also minimizes the largest load, despite the source’s introductory equivalence statement. For weights 4,4,4,6,6,9 in three bins, loads (10,10,13) attain the minimum range 3, while the minimum achievable largest load is 12, attained by (9,12,12), also with range 3. Thus a range-optimal tie can have a worse makespan. No lexicographic makespan tie-break is part of this record.
Scope
#reported-comparisons
The source compares C implementations of CGA and CKK on uniformly sampled integer inputs, with implementation-specific small-state termination and node-accounting choices. Its two-way and three-way results favor CKK in the studied regimes but do not establish an input-independent runtime ordering. Complete search does not imply that every additional node improves the incumbent, nor does a small average runtime imply a polynomial worst-case bound.
⚠️ Curated Limitations & Negative Results
- The bins are interchangeable, empty bins are allowed, and the objective is load range. Capacity constraints, equal cardinalities, bin-dependent costs and alternative objectives are outside this identity.
- The multiway average-based lower bound is generally optimistic; it is not an attainable solution or an optimality certificate by itself.
- Exact certification assumes exact arithmetic or conservative bounds. Integer divisibility supplies a lower bound, not a promise of perfect balance.
- The complete primary manuscript was read. The later final journal text and author implementation were not inspected; constructed arithmetic is not a performance replication.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No inspected AIO target denotes this arithmetic item-assignment search. Generic learned-model, task and function classes do not establish a justified mapping.
Search Scope: Compared all 442 pinned AIO and 589 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 63, 0, 0 lines. All distinct match contents were inspected. Semantic matching covered 67 AIO and 96 native definitions, with every matched definition read. 6 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. The named CGA performs complete item-to-bin assignment with a greedy successor order. It is distinct from generic DFS, discrepancy ordering and KK/CKK residual composition. Its two-way and multiway forms share this item-assignment mechanism and are retained in one range-minimization record; k-way bounds are not asserted to be attainable. Existing hits are neighboring records, rendered text and discovery leads. No suitable pinned AIO counterpart was identified.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:GraphLanguageModel
|
Graph-structured language modeling is distinct from arithmetic subpartition manipulation. |
AIO:ReasoningLLM
|
A language model with explicit reasoning is not a number-partitioning algorithm. |
AIO:NeuroSymbolicLLM
|
A neural-symbolic language-model architecture is not this nonlearning search or heuristic. |
AIO:MachineLearningTask
|
Balancing a given multiset does not learn a method from data. |
AIO:MathematicalFunction
|
An algorithm evaluating differences and choosing a partition is distinct from the mathematical functions it uses. |
AIO:ReinforcementLearning
|
There is no reward-based learned policy or exploration/exploitation learning in the curated deterministic procedure. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
korf1997
|
Richard E. Korf
|
primary paper
full_text
|
ID: https://doi.org/10.1016/S0004-3702(98)00086-1
sha256:00751dfacfb6…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-13T08:10:51Z
Updated: 2026-10-13T08:10:51Z
Source File:
data/curated/CompleteGreedyNumberPartitioning.yaml