Re: question on variation of subset sum problem

On Mar 28, 3:34 pm, "Babua" <pin...@xxxxxxxxxxxxx> wrote:
On Mar 27, 9:33 pm, "amandeep.par...@xxxxxxxxx"

<amandeep.par...@xxxxxxxxx> wrote:
Hi,

The problem I have is a variation of subset sum. Given $n$ numbers
a_1, a_2 , ..., a_n and b. Does there exists sets S_1 and S_2
disjoint, subsets of {1,2,...,n} such that

Sum_{i in S_1} a_i + 1/2 Sum_{i in S_2} a_i = b ?

I think this is a NP-complete problem but I cant seem to show it. Any
comments would be greatly appreciated. Thanks,

-aman

Put another extra element in to the set S of n numbers = 2*Sum_{i in
S}a_i = 2X (suppose).
Reduce subset sum problem with sum b to this problem with k = X + b.

Thanks.

--- Pinaki

====================================================================

Sorry I was wrong. The if part is correct. But in the only if part of
the
reduction we may have difficulty in extracting the answer for subset
sum
from the current problem.

The new element to be included in S is not needed at all.
The correct reduction will be:

Subset sum problem with sum b to the current problem with sum = N-b/
2 (Assume b is even)

Here I am using N instead of X which denote the sum of all elements of
S.

W.l.o.g we can assume b to even in subset sum problem. We can reduce
general subset
sum to the problem of subset sum with b is even.

The if part of the reduction is obvious.

To extract the answer of the subset sum we can give the following
proof:


Let S_1 = X U Y and S_2 = Z U W. Let the sum of elements of X, Y, Z, W
be denoted by
A, B, C, D.

Then we have the following 2 equations :

A + D/2 = N-b
B + C/2 = b/2

Since N = A + B + C + D

B + C + D/2 = b
B + C/2 = b/2

From the above two equations we have :

C + D = b

Thus the elements of the set S_2 will give the desired answer in the
only if part
of the reduction.

Thanks.

--- Pinaki

=================================================================================

.

Relevant Pages

  • Re: difficult problem
    ... Where is the "calculated field total price" or whatever that you want to sum ... in the report footer? ... > these details are sales with the pieces, price, reduction ... > for each articles that has been sold on this ticket. ...
    (microsoft.public.access.reports)
  • Re: Proposition for Nick (open): Why so little parallelism?
    ... |>> Don't assume that you are going to have all the elements of your sum ... It is very rare indeed for a simple reduction to be worth parallelising; ... the usual reason for doing it is that it is easy ('low hanging fruit'). ...
    (comp.arch)
  • Re: Exact sequence
    ... Gmath wrote: ... interger modulo n and + denote the direct sum.?? ...
    (sci.math)
  • Sums of RV, Convolution plots
    ... My goal is to visualize the sum of iid random variables which I denote L_i. ... Given that I only have the pdf, this is all done in MATLAB using covolutions. ...
    (comp.soft-sys.matlab)
  • Re: what is this equal to
    ... > Let C_N^i denote choose i out of N ... the known sum should start at 0: ... Don Coppersmith ... Prev by Date: ...
    (sci.math)