Complete Karmarkar–Karp
Algorithms AIMech:CompleteKarmarkarKarp DRAFT
Aliases: CKK
A complete anytime algorithm for two-way number partitioning that first follows Karmarkar–Karp differencing, then explores complementary sum branches over residual subpartitions, retaining the best partition and using sound bounds or exhaustive search to certify optimality.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 588 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 204, 120, 119 lines. All distinct match contents were inspected. Semantic matching covered 67 AIO and 95 native definitions, with every matched definition read. 6 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. The combined frontier entry and new KK heuristic are related prior work, not an existing CKK identity. This two-way complete anytime algorithm searches relative subpartition orientations by differencing and summing the largest residuals. It is distinct from the irreversible KK heuristic, complete greedy item assignment, generic DFS and discrepancy-order search. Multiway extensions remain separate leads. No suitable counterpart was found in the inspected pinned AIO graph.
Claims & Grounded Evidence
6 Claims
Mechanism
#difference-and-sum-branches
At a search state, select the two largest nonnegative residuals a>=b. The preferred child replaces them by a-b, representing opposite orientations of their partial partitions; the other replaces them by a+b, representing the same orientation. Keep residuals ordered and visit difference before sum in the source’s depth-first formulation. Repeated relative-orientation decisions cover all two-way partitions up to overall bin exchange. Bookkeeping is required to reconstruct original item assignments; this is not the complete greedy algorithm’s assignment of one raw item at a time.
Mechanism
#dominance-and-parity
For a current largest residual a with remaining-residual sum r, any completion has residue at least max(0,a-r). If a>=r, placing all remaining residuals opposite a attains a-r, so the subtree can be solved directly; a lower bound no better than the incumbent also permits pruning. With exact integer weights, all attainable residues have the parity of the original total, allowing immediate optimality certification at0 for an even total or1 for an odd total. This parity stopping rule is not a generic real-valued tolerance rule.
Limitation
#anytime-versus-optimal
The first difference-only solution has the KK residue; subsequent search may improve the incumbent, whose residue never increases. A time or node limit can return a useful feasible partition without proving optimality. Certification requires a matching valid lower bound or completion of the remaining search with sound pruning. Improvement is not guaranteed at each step, and the best partition need not be unique. In a constructed8,7,6,5,4 example, KK gives2 and complete search reaches0; stopping after one search node retains an uncertified2.
Limitation
#complexity-and-representation
The complete binary search has depth n-1 and can require exponentially many nodes. Depth-first organization supports a linear-space implementation with compact state and undo bookkeeping, but copying every residual list along the recursion is not itself a linear-space guarantee. Numeric bit complexity is separate from node counts. The source uses sorted arrays and special small-state termination in its implementation; these details do not turn exact partitioning into a polynomial-time algorithm.
Scope
#subset-sum-reduction-scope
For nonnegative weights of total s and a feasible subset-sum target c in[0,s], replace c by s-c when c<s/2 and append d=2c-s>=0. The augmented instance has a zero-residue two-way partition exactly when the original has a subset with the adjusted target, and complementation recovers the original target when needed. A nonzero optimum rules out that target only after optimality is certified; an interrupted positive incumbent does not. This decision reduction does not assert equality between nonzero partition residue and the original subset-sum error.
Scope
#historical-evaluation-boundaries
The reported C implementations compare CKK and complete greedy search on uniform random integer instances using a SunUltraSparcModel1. Fixed precision changes the probability of a perfect partition and can make larger sampled instances easier; this is not monotone or universal hardness. Figure6 averages improvement ratios over100 trials with50 48-bit numbers, reporting large gains from continued search. Those distribution-, precision- and hardware-specific results do not guarantee arbitrary instances finish quickly. Three-way experiments and discrepancy-order variants are described separately from this two-way depth-first identity.
⚠️ Curated Limitations & Negative Results
- Scope is the two-way, nonnegative, finite-instance depth-first formulation. Multiway composition, cardinality constraints and discrepancy ordering require separate identity assessment.
- Sound optimality claims assume exact arithmetic or rigorously conservative bounds. A floating-point near-zero residual is not automatically an exact certificate.
- Anytime availability begins with a complete feasible partition; a limited run need not improve KK or establish optimality. Stored reconstruction information is required to return the actual partition.
- The inspected primary is the31-page27June1997 manuscript. The later1998 journal DOI supplies bibliographic linkage, not a claim that final journal text or source code was inspected.
- All manuscript pages were read; small exact-integer checks were executed without author-code or historical performance replication. They illustrate boundaries rather than prove the general completeness theorem.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No inspected AIO class denotes this complete arithmetic number-partitioning search. Learned graph models, reasoning LLMs, learning tasks and functions do not identify the algorithm itself.
Search Scope: Compared all 442 pinned AIO and 588 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 204, 120, 119 lines. All distinct match contents were inspected. Semantic matching covered 67 AIO and 95 native definitions, with every matched definition read. 6 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. The combined frontier entry and new KK heuristic are related prior work, not an existing CKK identity. This two-way complete anytime algorithm searches relative subpartition orientations by differencing and summing the largest residuals. It is distinct from the irreversible KK heuristic, complete greedy item assignment, generic DFS and discrepancy-order search. Multiway extensions remain separate leads. No suitable counterpart was found in the inspected pinned AIO graph.
| 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-13T07:52:26Z
Updated: 2026-10-13T07:52:26Z
Source File:
data/curated/CompleteKarmarkarKarp.yaml