4
$\begingroup$

The covering design problem is as follows: We are given a universe $\mathcal{U}$ of size $n$. By $C(n,k,l)$ we denote the smallest cardinality of any set system $\mathcal{A} \subset 2^\mathcal{U}$ consisting of subsets of $\mathcal{U}$, such that all sets in $\mathcal{A}$ have size at most $l$ and each subset of $\mathcal{U}$ with size $k$ is contained in some set $A \in \mathcal{A}$.

For example, when $k = 2$ and $l = 4$ we are looking for a system of sets $\mathcal{A}$ in which each set has at most size 4 and for each pair of elements in $u_1, u_2 \in \mathcal{U}$ there exists a set $A \in \mathcal{A}$, such that $u_1, u_2 \in A$.

The covering design problem is related to Steiner Systems: In Steiner Systems we add the constraint that each subset of $\mathcal{U}$ of size $k$ is covered by exactly one set of $\mathcal{A}$.

We know that for fixed $k$ and $l$, asymptotically we have $$C(n,k,l) = O\left( {n \choose k} / {l \choose k} \right),$$ see [A]. Also, we know that a greedy algorithm with running time $O(n^l)$ computes $C(n,k,l)$ exactly [B]. However, this is superpolynomial in the output size $O(n^k)$ if $l = \omega(1)$ and $k$ is fixed. Hence my question:

Do we known an approximation algorithm for this problem which explicitly constructs a set system $\mathcal{A}$ within some approximation guarantee and has running time polynomial in the output size $O(n^k)$?

I am particulary interested in the case when $k =2$, i.e. when each pair of $\mathcal{U}$ must be contained in a set of $\mathcal{A}$.

In [C], the authors show that a similar problem cannot be approximated better than within a factor $O(\log n)$, unless $P = NP$.

[A] http://www.ccrwest.org/gordon/optimal.pdf
[B] http://arxiv.org/abs/math/9502238
[C] http://www.sciencedirect.com/science/article/pii/S0166218X04001180

$\endgroup$
  • $\begingroup$ @NealYoung: These are great observations, thank you! Indeed, there was a typo: The running time of the greedy algorithm is $O(n^l)$ (as it first enumerates all subsets of $\mathcal{A}$ of size $l$ and then prunes the superficial ones). Your second observation is also correct: The running time of the algorithm should be polynomial in the output size and independent of $l$. I really do want to explicitly construct a set system realizing the number. I have updated the question to be more accurate. $\endgroup$ – tranisstor Apr 16 '16 at 18:59
  • 2
    $\begingroup$ Looking at your reference [B], are you sure that the greedy algorithm they present constructs an optimal code? They say "Greedy coverings are not in general optimal, but as happens with codes ... they are often quite good—about 42% of the table entries come from greedy coverings". In a quick scan, I didn't see any performance guarantee there. $\endgroup$ – Neal Young Apr 17 '16 at 0:15
  • 2
    $\begingroup$ Perhaps you mean reference [A], which appears to give an (expected) $(1+o(1))$-approximation algorithm in section 2.1? It looks likely that with a little care that algorithm could be implemented in output-sensitive poly-time, at least for the case k=2 that you are interested in. To do so, don't you just need the following primitive? Given a collection $C$ of edge-disjoint $\ell$-cliques within a complete graph $G$ on $n$ vertices, choose a new $\ell$-clique uniformly at random from among the $\ell$-cliques that share no edges with the $\ell$-cliques in $C$. $\endgroup$ – Neal Young Apr 17 '16 at 0:27
  • 2
    $\begingroup$ Did you try replicating the logic used by Sauer's lemma? Order the elements $v_1, \ldots, v_n$. Let $V_i = \{v_1,\ldots, v_{i}\}$. Now, let $f(V_i,k',l')$ be the computed family of sets for the sets $V_i$. Now, abusing notations a lot, we have $F(V_n,k,l) = [F(V_{n-1}, k-1, l-1) \sqcup \{ v_n\}] \cup F(V_{n-1}, k, l)$. Here for a family of sets $F$, we denote by $F \sqcup \{x\}$ the family of sets resulting from adding $x$ to all sets. $\endgroup$ – Sariel Har-Peled Apr 17 '16 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.