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

  • $\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
    Commented Apr 16, 2016 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
    Commented Apr 17, 2016 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
    Commented Apr 17, 2016 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$ Commented Apr 17, 2016 at 18:02


Your Answer

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