Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
You might synchronize your indices. Gerhard "Ask Me About System Design" Paseman, 2012.03.28 –  Gerhard Paseman Mar 28 '12 at 20:55
    
you may want to post this on cs.stackexchange.com –  Kaveh Apr 18 '12 at 3:42
    
I have several questions about this problem. 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 –  user25450 Aug 21 '12 at 5:42
add comment

1 Answer

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

share|improve this answer
    
This paper is directly available at or.deis.unibo.it/alberto/mssp_g_f.ps –  Barry Cipra Oct 27 '12 at 13:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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