2
$\begingroup$

Given an array of $N$ elements, $A$, and a number $K$. ($1 \leq K \leq N$) .
Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum subset sum achievable out of $K$ partitions formed, must be the minimum possible.
Find that possible subset sum.

For example $A = [11, 11, 5, 10, 5]$ and $K = 2$ the partitioning that satisfies the problem will be $\{\{11, 5, 5\}, \{11, 10\}\}$ so that the defined maximum sum will be $21$ and it is the minimum of all different K-Partitionings of $A$.


The question came up to my mind when I was solving a similar problem for only K contiguous subarrays which could be easily solved using a binary search over all possible maximum sums of the array($O(\log{\text{SUM}})$).

For example for the same $A$ defined in above maximum sum is at least the maximum number which is $11$ and is at most the total sum of all elements which is $42$.

Then in each step of binary search we check whether it is possible to split $A$ into at most $K$ contiguous subarrays or not so that the maximum sum over all subarrays will be at most the mid point of binary search step(needs one loop over $A$ then $O(n)$). If yes we recurse on the left side, otherwise we recurse on the right side.
in overall the algorithm will have a $O(n\log{\text{SUM}})$ time complexity.
But I can't find a way to generalize the checking process in every step of the binary search so that it checks whether for a specific maximum sum like $s^{*}$ is it possible to partition $A$ with at most $K$ subsets so that the maximum sum over all subsets will be at most $s^{*}$ with a good time complexity.

I should also mention that the above motivation is not necessarily the only way accepted to solve this problem and every other idea will be appreciated.

$\endgroup$
3
  • $\begingroup$ Your problem is NP-hard by reduction from PARTITION. $\endgroup$ Commented Dec 11, 2021 at 20:31
  • $\begingroup$ So is there any NP solution for it? for example somehow using backtrack? @YuvalFilmus. $\endgroup$ Commented Dec 11, 2021 at 22:15
  • $\begingroup$ The NP solution is to try all possible splits. $\endgroup$ Commented Dec 12, 2021 at 8:19

2 Answers 2

0
$\begingroup$

Use backtracking to check all the possible combinations and using a heuristic function you can reduce the search space to reach answer quickly. I've used one such solution to distribute the load as an array of n elements evenly across k partitions. Let me know if you need the code as well.

$\endgroup$
0
$\begingroup$

This is a pretty typical assignment problem that can be framed as a MILP optimisation. You need constraints for exclusive coverage, minimum cardinality, and sum-maximum correlation:

import time

import numpy as np
from scipy.optimize import milp, Bounds, LinearConstraint
import scipy.sparse as sp

a = [11, 11, 5, 10, 5]
n = len(a)
k = 2

# Variables: n assignments * k subsets, 1 maxsum

cost = np.concatenate((
    np.zeros(n*k), # assignments themselves do not have a cost
    np.ones(1),    # minimise subset maximum
))

integrality = np.concatenate((
    np.ones(n*k, dtype=np.uint8),        # assignments are binary
    np.zeros(1, dtype=np.uint8),   # maximum is continuous
))

bounds = Bounds(
    # Assignments are binary, maximum is unbounded
    lb=np.concatenate((np.zeros(n*k), np.full(1, fill_value=-np.inf))),
    ub=np.concatenate((np.ones(n*k), np.full(1, fill_value=+np.inf))),
)

# Each element must be assigned exactly once
coverage_constraint = LinearConstraint(
    A=sp.hstack((
        sp.kron(np.ones((1, k)), sp.eye_array(n)),  # assignment identity matrices
        sp.csc_array((n, 1)),  # max does not participate
    ), format='csc'),
    lb=1, ub=1,
)

# Each subset must be of cardinality at least one
cardinality_constraint = LinearConstraint(
    A=sp.hstack((
        sp.kron(sp.eye_array(k), np.ones((1, n))),  # assignment identity matrices
        sp.csc_array((k, 1)),  # max does not participate
    ), format='csc'),
    lb=1,
)

# The maximum must be at least the sum of each subset:
# a.I <= max   0 <= max - a.I
sum_constraint = LinearConstraint(
    A=sp.hstack((
        sp.kron(
            -sp.eye_array(k),  # assignment identity matrices
            np.reshape(a, (1, n)),  # array values to sum
        ),
        np.ones((k, 1)),
    ), format='csc'),
    lb=0,
)

t0 = time.perf_counter()
result = milp(
    c=cost, integrality=integrality, bounds=bounds,
    constraints=(
        coverage_constraint, cardinality_constraint, sum_constraint,
    ),
)
t1 = time.perf_counter()
assert result.success, result.message

print(result.message)
print(f'Time: {1e3*(t1-t0):.1f} ms')
assign, (max_sum,) = np.split(result.x, (-1,))
print(f'Maximum sum: {max_sum}')
assign = (assign > 0.5).reshape((k, n)).astype(np.uint8)
print('Assignments:')
print(assign)
Optimization terminated successfully. (HiGHS Status 7: Optimal)
Time: 3.6 ms
Maximum sum: 21.0
Assignments:
[[1 0 1 0 1]
 [0 1 0 1 0]]

This has the following sparsity pattern:

plt.imshow(
    sp.vstack((
        coverage_constraint.A, cardinality_constraint.A, sum_constraint.A
    )).toarray().clip(min=-1, max=+1),
)
plt.show()

sparsity

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.