We are given a set of $n$ positive integers. We assume all of them are bounded by a polynomial of $n$. We would like to find a subset $S$ of numbers such that for any $T_1,T_2\subseteq S$, the sum of numbers in $T_1$ is not equal to that of $T_2$. We want the size of $S$ is maximized. Clearly, the problem is in NP and can be solved in $n^{O(\log n)}$ time (Since $|S|\leq O(\log n)$). Is this problem polynomial time solvable? Is this problem studied before? Any help is appreciated.
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
3
|
|
|
|
|
4
|
This has been studied, see http://www.mathnet.or.kr/mathnet/kms_tex/978590.pdf and the somewhat more interesting: NEWMAN POLYNOMIALS WITH PRESCRIBED VANISHING AND INTEGER SETS WITH DISTINCT SUBSET SUMS PETER BORWEIN AND MICHAEL J. MOSSINGHOFF (available online) See also the references in: http://garden.irmacs.sfu.ca/?q=op/sets_with_distinct_subset_sums None of these answers your question, but I think this is the state of the art... |
||
|
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
4
|
In the modern language, sets with all subset sums pairwise distinct are often called dissociated. Maximal dissociated subsets of a given set are important in Additive Combinatorics and Fourier analysis, although I cannot recall anybody ever addressing the algorithmic aspect. Yet another reference you may find useful: http://math.haifa.ac.il/~seva/Papers/DisBases.pdf. Added: taking into account the interpretation of a maximal dissociated subset of a given set $A$ as a "basis of $A$ over the set ${-1,0,1}$", it may be reasonable to try and adjust one of the standard algorithms of finding a maximal independent subset of a given set in a vector space. |
|||
|
|
