Optimize / simple Set Covering Problem

2011-06-30T11:07:34Z

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)?

I tried to construct a sequence of numbers which maximize $|T+T|$. But I couldn’t figure out:

Is it possible to cover the whole set $M$ for $k\leq \sqrt{m}$?
What is the best way to construct such a sequence in theory?

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

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.

In my opinion it is hard to find such an optimal subset $T$.

Sorry for my bad English.

Answer by quid for Optimize / simple Set Covering Problem

2011-06-30T17:43:05Z

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

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 $a_1+a_2 = a_3+a_4$ if and only if $\{a_1,a_2\} = \{a_3,a_4\}$ (the sets), in other words $(a_1,a_2)$ or $(a_2,a_1)$ is equal to $(a_3,a_4)$ (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).

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 $(k^2 - k)/2 + k$ [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.

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

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 $a_1=g-a_2$ with $a_i \in T$ 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).

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 Kevin O'Bryant's 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.

Optimize / simple Set Covering Problem - MathOverflow

Optimize / simple Set Covering Problem

Answer by quid for Optimize / simple Set Covering Problem