8
$\begingroup$

I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or differ only by 1 (if n is odd).

I think we can do this in pseudo polynomial time $O(n^2 A)$, where $A$ is the sum of numbers in the set.

Can I do better than this? Namely, is there a pseudo polynomial time algorithm that runs in time $O(n^c A)$ with $c < 2$?

Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ Notice that as a special case of Knapsack, it has an FPTAS. See e.g. E.L.Lawler. Fast approximation algorithms for knapsack problems. $\endgroup$ – Mathieu Chapelle Jan 30 '11 at 14:10
  • 1
    $\begingroup$ @Oleksandr , by better I meant is there a pseudo polynomial algorithm which runs in O(nA). sorry that i am unable to post in latex. $\endgroup$ – Firebrandt Jan 30 '11 at 16:38
  • 4
    $\begingroup$ I am afraid that this question is on the border of being too elementary. For example, “Is the Partition problem with the additional restriction that the two sets must have equal cardinality still NP-complete?” can be a typical homework question and I am afraid that writing down the answer may have negative impact on some courses in computational complexity. $\endgroup$ – Tsuyoshi Ito Jan 30 '11 at 20:55
  • 6
    $\begingroup$ How is this too elementary? The obvious approach gives $O(n^2A)$, and the question is whether there's a better algorithm running in time $O(n^c A)$ where $c < 2$. My guess is that this is an open question. $\endgroup$ – Peter Shor Jan 31 '11 at 19:27
  • 3
    $\begingroup$ @Firebrandt: I took the liberty of editing your original question to add my version of your clarification (changing $O(nA)$ to $O(n^cA)$ with $c<2$, since I think even that's probably an open question). Feel free to change it back to $O(nA)$ if you want. I think the question, as clarified by your comments, is clearly research-level. $\endgroup$ – Peter Shor Feb 1 '11 at 20:56
7
$\begingroup$

One can solve the decision problem in $\tilde{O}(nA)$ time.

Let the sequence of numbers be $S$. Define $F_S$ to be a set such that $(i,j)\in F_S$ iff there exist a subsequence of $S$ of length $j$ that sums to $i$. If we have computed $F_S$, then we just need $O(nA)$ additional time to go thorough $F_S$ to solve your problem.

If $S_1$ and $S_2$ are two subsequences that partitions $S$, then

$$F_S = F_{S_1} + F_{S_2}$$

where $A+B=\{a+b | a\in A, b\in B\}$ is the minkowski sum, and addition between tuples are defined coordinate-wise.

Claim: Computing $F_S$ from $F_{S_1}$ and $F_{S_2}$ takes $\tilde{O}(|S|A)$ time.

Proof: Apply 2D convolution on two tables of size $A\times |S|$.

The algorithm partition the sequence to two equal sized sequences, apply recursion to each, and take the minkowski sum of the result. Let $T_A(n)$ be the worst case running time when the input to the algorithm has $n$ elements and $A$ is an upper bound of the sum. We have
$$ T_A(n) = 2 T_A(n/2) + A \tilde{O}(n) $$ Which shows $T_A(n) = \tilde{O}(n A)$.

The hidden $\log$ factor is $\log n \log nA$.

$\endgroup$
3
$\begingroup$

If anybody care about the $\log$ factors, with careful analysis we can prove the time complexity for Chao's algorithm is $O(nA\log(nA))$.

Proof. At the even-th layer of the recursion tree, we partition the set $S$ into two equally sized set $S_1$ and $S_2$, which gives $$T_e(n,A)=T_o(n/2,A')+T_o(n/2,A-A')+O(nA\log(nA)),$$ and at the odd-th layer of the recursion tree, we partition the set $S$ into two "equally sumed" set $S_1$ and $S_2$. To be precise, we can partition a set $S$ with sum $A$ into two sets $S_1$ and $S_2$ with each of them sum up to $\leq A/2$, with at most one element left. We can deal with that element with trivial dynamic programming in $O(A)$. This gives $$T_o(n,A)=T_e(n_1,A/2)+T_e(n-n_1,A/2)+O(nA\log(nA)),$$ where $n_1=|S_1|$. Therefore we have $$T(n,A)\leq \sum_{i=1}^4T(n_i,A_i)+O(nA\log(nA)),$$ where $\sum_{i=1}^4n_i\leq n$, $\sum_{i=1}^4A_i\leq A$, and $\forall i,~n_i\leq n/2,~A_i\leq A/2$. This will give us $T(n,A)=O(nA\log(nA))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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