hi.....need help in proving this plz.....
- From: hank <frank_buf@xxxxxxxxx>
- Date: 21 Apr 2007 19:26:10 -0700
Name: Minimum Sum of Squares [SP19] 3-4
Input: A set A of n elements; for each element a in A a positive
integer size s(a); positive integers k<=n and J.
Question: Can A be partitioned into k disjoint sets A1,...,Ak such
that
sum from i=1 to k ( sum from {x in Ai} s(x) ) ^ 2 <= J ?
How can we reduce a known Np problem to this problem?
I was thinking of using partition....
wht do yu think?
.
- Prev by Date: Re: Reducing the Knapsack Problem to the Bin Packing Problem
- Next by Date: Timer Implementation
- Previous by thread: Re: Intractability Problem (reduction form 3SAT)
- Next by thread: Timer Implementation
- Index(es):