Paired differencing method
Algorithms AIMech:PairedDifferencing DRAFT
Aliases: PDM
A two-way number-partitioning heuristic that sorts residuals and differences disjoint adjacent pairs in whole rounds, carries an unpaired residual forward, and repeats until one residual remains, producing a partition whose subset cardinalities differ by at most one.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 592 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 9, 0, 4 lines. All distinct match contents were inspected. Semantic matching covered 67 AIO and 99 native definitions, with every matched definition read. 6 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. Paired differencing performs whole rounds of adjacent sorted pairs before reordering. The first round enforces two-bin cardinality balance; LDM/KK instead reorders after each largest-pair operation and need not balance cardinalities. The frontier phrase pairwise differencing in rounds is resolved here; package-manager PDM and license-string hits are unrelated. BLDM switches after only the first paired round and remains a separate lead. No matching AIO identity or justified mapping was found.
Claims & Grounded Evidence
6 Claims
Mechanism
#whole-round-selection
For a finite nonempty multiset of nonnegative weights, sort the current residual list. In one round, replace the largest and second largest by their nonnegative difference, the third and fourth largest by theirs, and so on. Carry the smallest unpaired residual unchanged if the list length is odd. Sort the resulting ceil(n/2) residuals and repeat, using the current list length at each round. Reordering occurs between complete rounds, unlike largest differencing after every pair.
Mechanism
#indexed-reconstruction
Each residual represents a signed difference of sums over disjoint original item groups. When a>=b is replaced by a-b, keep a’s positive group with b’s negative group, and a’s negative group with b’s positive group. Retain the merge tree or original-index bookkeeping to reconstruct the two final subsets; the residual alone does not identify them. Duplicate values and zero residuals still represent distinct original indices.
Scope
#cardinality-balance
The first paired round puts each paired original item on opposite sides of its partial partition, giving every such residual effective cardinality difference 0. For odd input size there is one unpaired original item with difference 1. Subsequent differencing can only add or subtract these signed differences, so the final absolute cardinality difference is0 for even size and1 for odd size. This guarantees balanced subset sizes, not equal subset sums. Zero-valued items still count toward cardinality.
Limitation
#feasible-not-optimal
The method retains one paired-differencing path and does not certify a minimum sum difference among balanced partitions. In a constructed run on 8,7,6,5,4 it returns loads 16 and 14, residue 2, while a balanced 2-versus3 partition can have 15 on both sides. More arithmetic after the final residual does not explore discarded pairing or orientation choices. Complete balanced search is a separate procedure.
Scope
#resource-scope
There are n-1 differencing operations. Sorting geometrically shrinking lists gives O(n log n) comparison/arithmetic work; a merge-tree implementation can retain O(n) nodes for reconstruction. These are unit-cost bounds and do not make arbitrary-precision integer arithmetic free. The supplied small indexed calculation illustrates memberships and scaling, not these implementation resource bounds.
Scope
#method-boundaries
PDM repeats paired rounds throughout. The original report’s Algorithm B describes this round-based idea for power-of-two input size; Mertens gives the paired-method description with odd-item carry. BLDM instead performs only the first paired round and then switches to largest differencing. Largest differencing alone need not balance cardinalities: on 100,10,9,8 the constructed largest-first result has sizes 1 and 3 with residue 73, while PDM has sizes 2 and 2 with residue 89. The original randomized compaction algorithm and cited average-case proofs are separate evidence; their guarantees are not inherited here.
⚠️ Curated Limitations & Negative Results
- The objective is two-bin sum difference with cardinalities differing by at most one. This does not cover arbitrary prescribed cardinality differences or multiway balance.
- Tie choices may change reconstructed memberships. The indexed examples specify stable sorting and do not reproduce an uninspected author implementation.
- The complete 12-page Mertens preprint and 30-page original report were read. Lueker and Yakir publication metadata/abstracts were located, but their full proofs were not inspected and no asymptotic residue claim is adopted.
- A heuristic result is a feasible balanced partition, not an optimality certificate. No runtime or average-case experiment was replicated.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No inspected AIO target identifies this deterministic paired residual procedure or its cardinality invariant.
Search Scope: Compared all 442 pinned AIO and 592 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 9, 0, 4 lines. All distinct match contents were inspected. Semantic matching covered 67 AIO and 99 native definitions, with every matched definition read. 6 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. Paired differencing performs whole rounds of adjacent sorted pairs before reordering. The first round enforces two-bin cardinality balance; LDM/KK instead reorders after each largest-pair operation and need not balance cardinalities. The frontier phrase pairwise differencing in rounds is resolved here; package-manager PDM and license-string hits are unrelated. BLDM switches after only the first paired round and remains a separate lead. No matching AIO identity or justified mapping was found.
| 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
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
mertens1999
|
Stephan Mertens
|
primary paper
full_text
|
ID: https://arxiv.org/abs/cs/9903011v1
sha256:fe0bcf132782…
|
karmarkar-karp-report
|
Narendra Karmarkar, Richard M. Karp
|
primary paper
full_text
|
ID: UCB/CSD-83-113
sha256:f6ca1d4198d4…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-13T08:26:29Z
Updated: 2026-10-13T08:26:29Z
Source File:
data/curated/PairedDifferencing.yaml