Complete multiway Karmarkar–Karp
Algorithms AIMech:CompleteMultiwayKarmarkarKarp DRAFT
Aliases: Multiway CKK
A complete anytime multiway number-partitioning search that combines partial bin assignments in alternative relative permutations, explores low-range compositions first, and uses normalized load bounds and symmetry to retain and certify a minimum-range partition.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 591 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 88, 0, 0 lines. All distinct match contents were inspected. Semantic matching covered 67 AIO and 98 native definitions, with every matched definition read. 6 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. This k>=3 complete vector-subpartition search explores relative bin permutations. It extends the maintained multiway heuristic with exhaustive alternatives and bounds; the scalar two-way CKK and raw-item CGA remain distinct. Text matches are neighboring records and the partly addressed combined multiway discovery lead. No suitable pinned AIO counterpart was identified.
Claims & Grounded Evidence
6 Claims
Mechanism
#permutation-search
For fixed k>=3 and finite nonempty nonnegative weights, represent each original item as a k-bin subpartition with one occupied bin. Select the two subpartitions with largest normalized maximum loads. Explore all relevant relative bin permutations, add aligned loads and merge their original memberships, normalize by subtracting the minimum, and reinsert the result. Search children in increasing new normalized maximum; the preferred composition pairs opposing ranks. Unlike CGA, a step combines already formed subpartitions rather than assigning one raw item.
Scope
#coverage-and-symmetry
A subpartition commits its represented items to relative bins; later composition can permute its bins but does not reunite bins that were kept apart. Exploring relative permutations covers all assignments up to interchangeable-bin symmetry before additional pruning. Equal normalized load states can have the same objective-search future even when their memberships differ. Such symmetry reduction preserves the optimal objective value, not enumeration of every distinct membership partition. Normalized zero can represent a nonempty minimum-load bin, so it cannot be used alone as an emptiness flag.
Mechanism
#admissible-load-bound
Across current normalized subpartitions, let M be the largest bin component and S the sum of all components. A lower bound on final range is max(0, M-(S-M)/(k-1)); a branch whose bound is at least the incumbent range cannot improve it. Subtracting a common offset from every bin of a subpartition preserves final range under any subsequent alignment. The average bound need not be attainable with indivisible item groups, and a small bound is not a feasible completion. Exact or conservative arithmetic is needed for sound pruning.
Limitation
#anytime-certification
The preferred path provides the multiway KK heuristic result, after which alternate compositions can improve it. A finite complete search with sound pruning certifies minimum range, while a limited run can retain an uncertified feasible incumbent. For integer inputs, attaining range 0 when the total is divisible by k, or range 1 otherwise, certifies a global lower bound; such balance need not exist. In a constructed three-bin example with weights 2,2,2,3,3,5, a one-node run retains range 2 without certification and complete search finds range 1. Worst-case search remains exponential.
Limitation
#range-objective
The optimized objective is largest load minus smallest load. For k>=3, a minimum-range solution need not minimize the absolute largest load. Weights4,4,4,6,6,9 permit range-optimal loads (10,10,13) with range 3, while minimum makespan 12 is attained by (9,12,12). A complete range search may retain the former tie, so the source’s introductory objective-equivalence assertion is not adopted as a guarantee.
Scope
#reported-evaluation-scope
The source’s three-way CKK/CGA comparison uses 100 random trials per point with integer values uniformly drawn from 0 through 100000. The implementations differ in per-node cost; CKK’s smaller search need not imply universally cheaper node generation. The reported difficulty peak and practical speedups depend on bin count, precision, distribution and implementation. No universal runtime ordering or arbitrary-instance practical bound follows.
⚠️ Curated Limitations & Negative Results
- This identity concerns unconstrained range minimization for k>=3 interchangeable bins; empty bins are allowed. Cardinality and bin-specific constraints require additional state and proofs.
- Optimal objective coverage and unique enumeration of item memberships are different guarantees. Equal-load pruning preserves only the former scope here.
- Normalization needs separate membership or offset bookkeeping to reconstruct absolute loads. A normalized zero is not necessarily empty.
- Constructed fixed examples validate stated distinctions only. The complete 31-page primary manuscript was read; final journal full text, author code and empirical replication were not inspected or run.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No inspected AIO class denotes complete arithmetic permutation search over partial bin assignments.
Search Scope: Compared all 442 pinned AIO and 591 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 88, 0, 0 lines. All distinct match contents were inspected. Semantic matching covered 67 AIO and 98 native definitions, with every matched definition read. 6 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. This k>=3 complete vector-subpartition search explores relative bin permutations. It extends the maintained multiway heuristic with exhaustive alternatives and bounds; the scalar two-way CKK and raw-item CGA remain distinct. Text matches are neighboring records and the partly addressed combined multiway discovery lead. 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:25:39Z
Updated: 2026-10-13T08:25:39Z
Source File:
data/curated/CompleteMultiwayKarmarkarKarp.yaml