Optimize / simple Set Covering Problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T09:40:56Z http://mathoverflow.net/feeds/question/69174 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69174/optimize-simple-set-covering-problem Optimize / simple Set Covering Problem greedyplot 2011-06-30T11:07:34Z 2013-02-02T15:36:57Z <p>Let $k,m\in\mathbb{N}$ be given. Let $M:=\{0,... , m-1\}$. How to find a subset $T\subset M$, $|T|=k$ such that $|T+T|$ is maximal, where $T+T=\{ (a+b)\mathbin\%m \mid a\in T,b\in T \}$ (“%” means modulo)?</p> <p>I tried to construct a sequence of numbers which maximize $|T+T|$. But I couldn’t figure out:</p> <ul> <li>Is it possible to cover the whole set $M$ for $k\leq \sqrt{m}$?</li> <li>What is the best way to construct such a sequence in theory?</li> </ul> <p>I am looking for papers which deals with this topic or any word to find those papers. I don’t think this problem is running under the ordinary topic name “set covering problems”.</p> <p>My idea to construct such a sequence is $a_0=0;a_{i+1}=a_i+(k-i)$ for $T=\{a_i\mid i=0,...,k-1\}$ to get as small number of collisions as possible among the sums in $T+T$. But random subsets of $M$ show me that there are better subsets.</p> <p>In my opinion it is hard to find such an optimal subset $T$.</p> <p>Sorry for my bad English.</p> http://mathoverflow.net/questions/69174/optimize-simple-set-covering-problem/69208#69208 Answer by quid for Optimize / simple Set Covering Problem quid 2011-06-30T17:43:05Z 2011-06-30T17:43:05Z <p>A relevant keyword in this context is Sidon set (however Sidon is also used in a different context, so when searching do not be surprised if you stumble also over unrelated things).</p> <p>A subset $T$ of an abelian group $G$, written additively, in your case $\mathbb{Z}/m \mathbb{Z}$ with addition, is called a Sidon set if for $a_1,a_2,a_3,a_4 \in G$ one has <code>$a_1+a_2 = a_3+a_4$</code> if and only if <code>$\{a_1,a_2\} = \{a_3,a_4\}$</code> (the sets), in other words <code>$(a_1,a_2)$</code> or <code>$(a_2,a_1)$</code> is equal to <code>$(a_3,a_4)$</code> (the pairs). Or, verbally, their is no non-trivial way that two sums can be equal (the trivial one being of course that the summands are just flipped).</p> <p>In yet another way, a simple upper bound for $|T+T|$ is, for $|T|=k$, the expression $k(k+1)/2$, arising as ($k$ choose $2$) plus $k$ [the sum of the elements of two-element subsets plus the 'symmetric sums'] or equivalently <code>$(k^2 - k)/2 + k$</code> [half the number of pairs with distinct entries plus those pairs with twice the same entry]. Then, a Sidon set is a set that attains this upper bound. For a Sidon set $|T+T|$ is maximal among all elements of this cardinality, and one knows the cardinality precisely. </p> <p>This upper bound also answers one of your questions. For $k \le \sqrt{M}$, one has the upper bound for $|T+ T|$ of the form $(M + \sqrt{M})/2$ which is less than $M$ (except for $1$). So for $k \le \sqrt{M}$ you can never get all elements (except for $M=1$).</p> <p>Thus to some extent your question is really about Sidon sets. However, if $k$ is too large relative to $M$ the problem arises that no Sidon sets of that cardinality exists anymore. For very large $k$, the problem becomes 'cheap'. For example if $k > |G|/2$, then you have that $T\cap (g - T)$ is nonempty for each element of $g$ of $G$ and, thus, since <code>$a_1=g-a_2$</code> with <code>$a_i \in T$</code> one has in fact $g \in T+T$ and $T+T$ is the full group, and of course cannot be larger. Since this argument works for each set this can of course be improved (considerably). A key-word here would be 'additive basis of order two'. I do not continue on this as it seems to me, you care more about small $k$ (in a relative sense).</p> <p>Regarding your second question, on construction, this is an open problem (towards which however various results are known). The problem is that the precise maximal cardinality of a Sidon set is not known. So you do not know up to which exact value the bound $(k+1)k/2$ will actually be the right value. However, there are good constructions for Sidon sets known, and perhaps this is sufficient for you. For a detailed overview of results on Sidon-related resuls see <a href="http://www.emis.ams.org/journals/EJC/Surveys/ds11.pdf" rel="nofollow">Kevin O'Bryant's</a> annotated bibliography (many mant references). Note however that it is mainly on results in the integers (Sidon sets in the first $n$ integers, or infinite ones, then often called Sidon sequences). Yet, it also contains a section on cyclic groups and in part the results on integers are relevant too. </p>