[Model] SumOfSquaresPartition

[isPANN]

Motivation

MINIMUM SUM OF SQUARES (P146) from Garey & Johnson, A3 SP19. Given a finite set of positive integers and bounds K (number of groups) and J, the problem asks whether the set can be partitioned into K groups such that the sum of the squared group sums is at most J. This is NP-complete in the strong sense, making it harder than weakly NP-complete problems like PARTITION. The squared objective penalizes imbalanced partitions, connecting this problem to variance minimization, load balancing, and k-means clustering. It generalizes PARTITION (K=2, J=(S/2)^2 + (S/2)^2) and 3-PARTITION (K=n/3 with cardinality constraints).

Associated reduction rules:

• As target: R84 (PARTITION to MINIMUM SUM OF SQUARES)

Definition

Name: SumOfSquaresPartition

Canonical name: Minimum Sum of Squares
Reference: Garey & Johnson, Computers and Intractability, A3 SP19

Mathematical definition:

INSTANCE: Finite set A, a size s(a) in Z^+ for each a in A, positive integers K <= |A| and J.
QUESTION: Can A be partitioned into K disjoint sets A_1, A_2, ..., A_K such that
Sum_{i=1}^{K} (Sum_{a in A_i} s(a))^2 <= J ?

Variables

• Count: n = |A| (each element must be assigned to one of K groups)
• Per-variable domain: {0, 1, ..., K-1} — the index of the group to which the element is assigned
• dims(): vec![num_groups; sizes.len()] — each element is assigned to one of K groups.
• evaluate(): Partition elements by group assignment. For each group, compute the sum of its elements' sizes, then compute the sum of squares of all group sums. Return true iff the sum of squares <= bound.

Schema (data type)

Type name: SumOfSquaresPartition
Variants: none

Field	Type	Description
sizes	Vec<i64>	Positive integer size s(a) for each element a in A
num_groups	usize	Number of groups K in the partition
bound	i64	Upper bound J on the sum of squared group sums

Size fields (getter methods for overhead expressions):

• num_elements() → |A|
• num_groups() → K

Notes:

• This is a satisfaction (decision) problem matching the GJ formulation: Metric = bool, implementing SatisfactionProblem.
• A configuration is satisfying if it forms a valid K-way partition with Sum_{i=1}^{K} (Sum_{a in A_i} s(a))^2 ≤ J.

declare_variants! guidance:

crate::declare_variants! {
    SumOfSquaresPartition => "num_groups^num_elements",
}

Complexity

• Best known exact algorithm: NP-complete in the strong sense, so no pseudo-polynomial time algorithm exists unless P = NP. For fixed K, the problem is solvable in pseudo-polynomial time via dynamic programming with complexity O(n * S^(K-1)), where S = Sum s(a). For general K, brute-force enumeration of all K^n partitions with pruning (Stirling numbers of the second kind bound the distinct partitions). The Korf-Schreiber-Moffitt hybrid algorithms (CKK + branch-and-bound, 2018) provide practical improvements for the related multiway number partitioning problem. Asymptotic worst case: O(K^n) for general K and n.

Specialization

• PARTITION is a special case with K = 2 and J = S^2 / 2 (achievable iff a balanced partition exists, since (S/2)^2 + (S/2)^2 = S^2/2 is the minimum).
• 3-PARTITION can be seen as a related problem with K = n/3 and a cardinality constraint (each group has exactly 3 elements).
• The problem remains NP-complete in the strong sense when the exponent 2 is replaced by any fixed rational alpha > 1 (Wong & Yao, 1976).
• Variants replacing the K bound with a bound B on maximum set cardinality or maximum set size are also NP-complete in the strong sense.

Extra Remark

Full book text:

INSTANCE: Finite set A, a size s(a) in Z^+ for each a in A, positive integers K <= |A| and J.
QUESTION: Can A be partitioned into K disjoint sets A_1,A_2,...,A_K such that
Sum_{i=1}^{K} (Sum_{a in A_i} s(a))^2 <= J ?
Reference: Transformation from PARTITION or 3-PARTITION.
Comment: NP-complete in the strong sense. NP-complete in the ordinary sense and solvable in pseudo-polynomial time for any fixed K. Variants in which the bound K on the number of sets is replaced by a bound B on either the maximum set cardinality or the maximum total set size are also NP-complete in the strong sense [Wong and Yao, 1976]. In all these cases, NP-completeness is preserved if the exponent 2 is replaced by any fixed rational alpha > 1.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all partitions of n elements into K groups; compute sum-of-squares for each and check <= J.)
• It can be solved by reducing to integer programming. (Integer variables x_i in {0,...,K-1} for group assignment; auxiliary variables for group sums; quadratic constraint on sum of squares, linearizable via standard techniques.)
• Other: For fixed K, pseudo-polynomial DP in O(n * S^(K-1)) time.

Example Instance

Input:
A = {a_1, a_2, a_3, a_4, a_5, a_6} with sizes s = {5, 3, 8, 2, 7, 1} (n = 6 elements)
Total sum S = 5 + 3 + 8 + 2 + 7 + 1 = 26
K = 3 groups, J = 240.

Feasible partition:
A_1 = {a_3, a_6} = {8, 1}, group sum = 9, squared = 81
A_2 = {a_1, a_4} = {5, 2}, group sum = 7, squared = 49
A_3 = {a_2, a_5} = {3, 7}, group sum = 10, squared = 100
Sum of squares = 81 + 49 + 100 = 230 <= 240 = J. YES.

Infeasible with tighter bound J = 225:
The balanced partition above gives 230 > 225. The perfectly balanced partition would need group sums (26/3 ~ 8.67), which is impossible with integers. The best achievable is sums {9, 9, 8} giving 81 + 81 + 64 = 226 > 225. So for J = 225 the answer is NO.

Answer: YES for J = 240 (the partition {8,1}, {5,2}, {3,7} with sum-of-squares 230 witnesses feasibility).

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in reduction graph; connects to PARTITION via planned reduction R84
Non-trivial	✅ Pass	Distinct from existing problems — unique squared-sum objective over K-way partition
Correctness	⚠️ Warn	Wong & Yao 1976 reference not independently verified online (likely real — cited by G&J); Korf-Schreiber-Moffitt 2018 confirmed (JACM 65(4)); complexity section lacks a concrete best-known exact bound for declare_variants!
Well-written	⚠️ Warn	Minor issues: problem is framed as satisfaction (decision) but naming uses Minimum prefix suggesting optimization; complexity section does not provide a single concrete exponential bound needed for declare_variants!

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The problem does not exist in the codebase. MinimumSumOfSquares is a classic NP-complete problem (Garey & Johnson SP19) with connections to load balancing, k-means clustering, and variance minimization. The planned reduction from PARTITION (R84) would connect it to the existing reduction graph. The motivation section is substantive and explains the relationship to PARTITION and 3-PARTITION.

Non-trivial

This is genuinely distinct from all existing problems. The feasibility constraint (K-way partition) combined with the squared-sum objective is not equivalent to any current problem in the codebase. It is not a variant of BinPacking (which minimizes bins, not sum of squares), nor of any set-based or graph-based problem currently implemented.

Correctness

Garey & Johnson SP19: The book reference is standard and trustworthy. The problem statement matches the known G&J formulation (Appendix A, problem [SP19]).

Wong & Yao 1976: This reference appears in the G&J book's comment on SP19, but I could not independently locate the original paper online to verify the specific claim about rational exponents α > 1. This is likely a legitimate citation from the G&J commentary, but cannot be independently confirmed. ⚠️

Korf, Schreiber & Moffitt (2018): Confirmed. Published as "Optimal Multi-Way Number Partitioning" in JACM 65(4):24:1-24:61. The paper addresses multiway number partitioning (minimizing makespan), which is a related but different objective from sum of squares. The issue correctly says "related" rather than claiming it directly solves this problem.

Complexity bound: The issue states O(K^n) worst-case for general K, which is correct for brute-force. However, for declare_variants!, the project requires a concrete best-known exact algorithm bound (e.g., "K^num_elements") rather than a prose description. The complexity section is written in paragraph form rather than providing a single clear bound.

Example verification: The worked example is correct:

• Partition {8,1}, {5,2}, {3,7} gives sums 9, 7, 10 → 81 + 49 + 100 = 230 ≤ 240 ✓
• Best partition {8,1}, {7,2}, {5,3} gives sums 9, 9, 8 → 81 + 81 + 64 = 226 > 225 ✓ (confirms the NO answer for J=225)

Well-written

Strengths:

• All template sections are present and substantive
• The mathematical definition is clear and complete
• The example is well-worked with both YES and NO cases
• Symbol usage is consistent (A, s(a), K, J used throughout)

Issues (warnings, not failures):

1. Satisfaction vs. optimization naming ambiguity: The problem is defined as a decision/satisfaction problem (answer YES/NO), which means it should implement SatisfactionProblem with Metric = bool. However, the name uses the Minimum prefix, which by project convention implies an optimization problem with Direction::Minimize. The issue should clarify: is this a satisfaction problem (as the G&J definition states) or should it be reformulated as an optimization problem that minimizes the sum of squares? If satisfaction, the name should drop the Minimum prefix (e.g., just SumOfSquares). If optimization, the definition needs to be restated as "minimize Σ(group sums)² subject to K-way partition."

2. Complexity for declare_variants!: The complexity section provides a prose discussion but no single concrete bound string. For implementation, a specific expression like "K^num_elements" is needed.

3. Size fields not specified: The Schema section lists fields but doesn't explicitly name the getter methods that would appear in declare_variants! overhead expressions (e.g., num_elements(), num_groups()).

Recommendations

• Clarify whether this is a satisfaction problem (keep G&J decision formulation, rename to SumOfSquares) or an optimization problem (rename keeps Minimum prefix, reformulate as minimizing Σ squares). Given project conventions, optimization formulation is likely more useful for reductions.
• Add a concrete complexity string for declare_variants!, e.g., "K^num_elements" for brute-force.
• Specify the getter method names that overhead expressions will reference.

[isPANN]

Changelog (fix-issue-batch)

• Changed weight type from generic W to concrete i64 (G&J defines sizes as Z⁺; no need for float variants)
• Removed variant annotation (no type parameter)
• Formatted declare_variants! as proper code block