Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer

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...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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