4
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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