(NP) hard partitioning problem?

segments. You can choose from a set of line segments {L1, L2, L3, ...} where

L1 = ? L2 = L1*2, L3 = L2*2, L4 = L3*2, L5 = L4*2 ... and so on. These are the line segments you are allowed to choose from to form the line of length N. You must first choose some value for the first segment, L1. Then the second segment will be twice as large, the third segment twice the length of the second one, and so on.

The goal is to maximize the number of line segments.

Example: N = 15

L1 = 3 L2 = 3*2 = 6 L3 = 6*2 = 12 L4 = 12*2= 24 ...

Solution: L1 + L3 = 3 + 12 = 15

So the problem is to a) choose the appropriate L1 and b) choose the segments that results in a line of length N.

How, in general, do you solve this problem? I conjecture that there are no polynomial-time algorithm for this one, but I am not able to prove it.

Thanks in advance for any ideas!

I'm assuming that you're talking about using no more than one segment of each type, otherwise it's obviously trivial, and only integer lengths, otherwise it's unsolvable.

Okay. So essentially, you've got a set of integers S(x)= {x,2x,4x,8x,...,x*2^n,...} and a value N, and you want to choose x and a subset P of S which sums to N such that P is maximal.

Okay. Well, obviously x N, so let's start by supposing N=kx, so we have k=sum(2^i) for some set of integer i. This is a unique sum, equivalent to representing k in binary. So what we're looking for is the divisor x of N such that N/x has a representation in binary with a maximal number of 1's.

Sounds pretty polynomial to me.

Sorry, that was a stupid final statement. But still, the algorithm is fairly straightforward, polynomial or not.

Just to choose an example at random: N=90

As a starting point, powers of 2 can be discounted, as they leave the number of '1's unchanged in the binary representation. So this is equivalent to N=45

Divisors of N are 1,3,5,9,15 In binary, these are 1, 11, 101, 1001, 1111. So the best value for k is 15, which gives a best value for x of 3x2=6. (bringing back the power of 2 we ignored at the start)

Thus 90=6+12+24+48 is maximal.

Perhaps I'm missing something, but why wouldn't

L1+L2+L3+L4 = 1+2+4+8 = 15 be a better solution?

(I'm assuming you intend L1 to be a positive integer.)

Maybe you give us a little more details.

Can you choose a line segment from the set several times ? Is L1 an integer ?

If that is so and if you really want to MAXIMIZE the number of line segments, then choose L1=1 and you have N segments of length L1.

Minimizing the number of line segments seems to be more interesting.

...> > The goal is to maximize the number of line segments.

Yes, only integer solutions are interesting and, yes, I agree that minimizing is more interesting. But I'm actually happy if someone can provide a general way of finding ANY solution!

Note that L1 < N so you need more than one segment. You can NOT choose the same line segment more than once.

- han

Your assumptions are correct.

Nice work. But clearly not polynomial, since you must first find the divisors.

A correction: I'm actually more interesting in minimizing, but L1 < N so you need at least two segments.

You're right. But as noted by others, it's more interesting to minimize. Note that L1 < N so you need more than one segment. You may choose each line segment only once.

> minimizing is more interesting. But I'm actually happy if someone can > provide a general way of finding ANY solution!

Let L1 = 1. Then L_i = 2^(i-1), which gives us all whole powers of two. Write N in binary, which gives the sum of powers of 2 that form N. The solution maximizes the number of L's in the sum.

Why would this maximise the number of L's? Take N=33. Setting L1=1 uses only two L's (1+32), but setting L1=3 uses three (3+6+24).

It isn't hard to prove that if m = (2^k)r, where r is odd, then N=2^m+1 uses only two L's for L1=1, and exactly 1+(m-2^k)/2 L's for L1=2^2^k+1.

One thing I haven't seen mentioned yet is that the bottleneck in the current suggested solution (which I can't imagine any improvement on) is not in the factoring, but in enumerating all the divisors of N.

Factoring can be done in time O(exp(n^(1/3+eps))) in the length of N, but the number of divisors can be as high as exp(cn/log n) in the worst case. It would be interesting to know if the problem or some variant could be solved faster than explicitly testing every divisor.

I'm wrong. Don't know what I was thinking.