3
$\begingroup$

I would like to have a proof of the NP-completeness for 15-Partition Problem.

It is analogous to the well-known 3-Partition Problem. The problem is to decide whether a given multiset of integers can be partitioned into subsets of 15 members that all have the same sum. More precisely, given a multiset S of n = 15 m positive integers, can S be partitioned into m subsets of 15 members S1, S2, …, Sm such that the sum of the numbers in each subset is equal?

It is not an excercise, it is a real problem dealing with load balancing. I did not expect someone would suspect it as a homework/excercise. I mentioned only related facts, obviously, I need to say more. I have a hardware switch with 15 ingoing ports and one outgoing port. Such switches, I have actually 6. That means, I have 15 x 6 = 90 ingoing ports. I have to connect cabels to these 90 ports and I can not affect how much data flows throught these 90 cabels. My task is to assign these 90 cabels to these 90 ports such that the output flow from each switch would be equal. I have already implemented 4 algorithms solving this problem based on dynamic programming, integer linear programming, differential evolution and reinforcement learning.

I would like to have an exact proof that the problem is not so easy to solve, i.e., I would like to prove it belongs to NPC.

Moreover, I have realized today, in case of total flow is not divisible by 6, all switches will not have the equal sum of flow on outgoing port. For example, total flow is 456 254 bytes, then Switch1 to Switch2 should have flow 76 043 bytes each and Switch3 to Switch6 should have flow 76 042 bytes. So maybe, I can not use 15-Partition Problem, not sure about it.

Improve this question
$\endgroup$
2
  • $\begingroup$ Perhaps you can adjust one of the reductions found here to your situation: cs.stackexchange.com/a/19095/755, cs.stackexchange.com/q/783/755. $\endgroup$
    – D.W. ♦
    Commented Dec 30, 2017 at 21:49
  • $\begingroup$ Regarding the theoretical hardness of this problem, it is not a problem that the answer to an instance can be "NO" ("No partition exists") -- in fact, this is expected. The problem is strongly NP-hard, by rotia's reduction from 3-Partition. It may however be a problem in practice, assuming you want to do "something sensible" (rather than just print "No solution exists") in the case where no exact 15-partition exists. $\endgroup$
    – j_random_hacker
    Commented Jan 31, 2018 at 15:26

2 Answers 2

Reset to default
4
$\begingroup$

I think this could work.

We multyply all the numbers by fifteen and we also multiply $B$, the quantity that each "bucket" should add to, by fifteen and we add twelve to it. Then we add twelve numbers of size one for each bucket to the input.

As twelve is less than fifteen, we have to use exactly twelve of them to fill each bucket, then we have to use other three numbers to fill each bucket. As random_hacker says in the comment, if we use more than twelve numbers in a bucket, we will not be able to cover the gaps in another bucket and so that bucket won´t be able to reach the quantity it should reach.

We see that if the big numbers fill the buckets in 15-partition, they also fill the buckets in 3-partition. Also, if we put four or more big numbers in a bucket, we will have more than fifteen numbers in that bucket

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ +1. Since 3-Partition is strongly NP-hard, this shows that 15-Partition is too -- this means that a "fast in practice" pseudopolynomial-time DP algorithm (like for Knapsack) is unlikely to exist. One extra step in the proof sketch would be to say that no bucket can use more than 12 small numbers, since this would mean at least one bucket must violate its sum constraint by the pigeonhole principle. $\endgroup$
    – j_random_hacker
    Commented Jan 31, 2018 at 15:16
0
$\begingroup$

A lot of the difficulty of partitioning problems comes from the fact that someone wants exactly equal sum.

It is probably quite easy to find good approximations. Connect the six cables with the highest load. Add six more cables: the highest load to the lowest load box, then five more to match that total as close as possible. Repeat. Another 13 times. Check if that is good enough.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for you reply. As I have said, I have already implemented 4 algorithms giving precise solution, however, I am interested in how complex such problem actually is. $\endgroup$
    – Ondřej Šubrt
    Commented Nov 30, 2017 at 20:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.