Welcome to MathOverflow

Question

1

Given two sets of nonnegative integer numbers:

$X = {x_1, x_2, ... x_n}$ $Y = {y_1, y_2, ... y_m}$

Need to find partition of $X$ on $m$ disjoint subsets, such as sum of elements in $i$-th subset equal to $y_i$.

This generalization of Subset sum problem, which is known to be NP-Complete. One of the probable way of solving is to reduce it to system of integer linear equalities. But it's even more general and really hard to solve task. May be one has some fresh ideas?

edited Mar 29 2012 at 13:43

asked Mar 28 2012 at 20:35

Wisdom's Wind
39●2

	You might synchronize your indices. Gerhard "Ask Me About System Design" Paseman, 2012.03.28 – Gerhard Paseman Mar 28 2012 at 20:55
	you may want to post this on cs.stackexchange.com – Kaveh Apr 18 2012 at 3:42

Selda · Answer 1 · 2012-10-26 21:44:32Z UTC

2

http://dx.doi.org/10.1016/S0020-0190(00)00010-7

answered Oct 26 at 21:44

Selda
21●1

This paper is directly available at or.deis.unibo.it/alberto/mssp_g_f.ps – Barry Cipra Oct 27 at 13:10

dokelung · Answer 2 · 2012-08-21 05:42:14Z UTC

I have several questions about this problem, but I lack the MO reputation to leave comments. I have already had a decision procedure for this problem, but I call it multi-target subset sum problem. It is my research topic. I wonder that where did you encounter this problem or any application about this. Maybe we can discuss it here or in email. Thank you! My email: dokelung@gmail.com

Multiple disjoint subset sum problem

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.