| |
Composing
Equipotent Teams |
| |
|
| Authors: |
Mark
Cieliebak, Stephan Eidenbenz, and Aris Pagourtzis |
| Reference: |
In
"Proceedings of the 14th International Symposium on Fundamentals of Computation
Theory (FCT 2003)", Malmö, Sweden, August 2003. Springer, LNCS 2751,
pp. 98-108, 2003 |
| Download: |
Postscript
(.ps) or PDF (.pdf) |
| Abstract: |
We study the computational complexity of k Equal Sum Subsets, in
which we need to find k disjoint subsets of a given set of numbers
such that the elements in each subset add up to the same sum. This problem
is known to be NP-complete. We obtain several variations by considering
different requirements as to how to compose teams of equal strength to play
a tournament. We present:
- A pseudo-polynomial time algorithm for k Equal Sum Subsets
with k = O(1) and a proof of strong NP-completeness for k
= \Omega(n).
- A polynomial-time algorithm under the additional requirement that
the subsets should be of equal cardinality c = O(1), and a
pseudo-polynomial time algorithm for the variation where the common
cardinality is part of the input or not specified at all, which we proof
NP-complete.
- A pseudo-polynomial time algorithm for the variation where we look
for two equal sum subsets such that certain pairs of numbers are not
allowed to appear in the same subset.
Our results are a first step towards determining the dividing lines between
polynomial time solvability, pseudo-polynomial time solvability, and strong
{\sf NP}-completeness of subset-sum related problems; we leave an interesting
set of questions that need to be answered in order to obtain the complete
picture. |
| Remarks: |
|