This problem is a special case of Set Cover, and there is a simple greedy approximation algorithm. If we denote the kth harmonic number as H_k = ∑_i=1^k 1/i, the greedy algorithm achieves an approximation ratio H_n² = 2 ln n + Θ(1).

A better approximation ratio can be obtained by an approximation algorithm for k-Set Cover [DF97], which results in an approximation ratio H_n−1/2 = ln n + Θ(1).

Moreover, this is optimal in the following sense:

[DF97] Rong-Chii Duh and Martin Fürer. Approximation of k-set cover by semi-local optimization. In _Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC), pp. 256–264, May 1997. http://dx.doi.org/10.1145/258533.258599

[Fei98] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–652, July 1998. http://dx.doi.org/10.1145/285055.285059

This problem is a special case of Set Cover, and there is a simple greedy approximation algorithm [Joh74]. If we denote the kth harmonic number as H_k = ∑_i=1^k 1/i, the greedy algorithm achieves an approximation ratio H_n = ln n + Θ(1). (There is an algorithm [DF97] which results in a slightly better approximation ratio H_n−1/2.) (Edit: Revision 2 and earlier stated the approximation ratio of the greedy algorithm worse than the correct value.)

Moreover, this is almost optimal in the following sense:

[DF97] Rong-Chii Duh and Martin Fürer. Approximation of k-set cover by semi-local optimization. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC), pp. 256–264, May 1997. http://dx.doi.org/10.1145/258533.258599

[Fei98] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–652, July 1998. http://dx.doi.org/10.1145/285055.285059

[Joh74] David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256–278, Dec. 1974. http://dx.doi.org/10.1016/S0022-0000(74)80044-9

Let n=2m+2. For E⊆[m+1], let P_E be the n×n permutation matrix which is block diagonal with n 2×2 blocks so that ith block is $\pmatrix{0 & 1 \\ 1 & 0}$ if i∈E and $\pmatrix{1 & 0 \\ 0 & 1}$ otherwise. Let Q be the n×n permutation matrix whose (i, i+2)-entry is 1 for all 1≤i≤n (where the index i+2 are interpreted as modulo n). For 0≤j≤m, define S_j = {P(E)Q^j: E∈C∪{{m+1}}} and S = S₀∪…∪S_m.

Proof sketch. If D⊆C is a cover of [m], we can construct a cover T⊆S of size (|D|+1)(m+1) by T = {P(E)Q^j: E∈S∪{{m+1}}, 0≤j≤m}.

On the other hand, let T⊆S be a cover. Note that all the matrices in S₀ are block diagonal with blocks of size 2×2, and the other matrices in S have 0 in these blocks. Therefore, T∩S₀ covers these blocks. Moreover, T∩S₀ contains P({m+1}) since otherwise the (2m+1, 2m+2)-entry would not be covered. Observe that (T∩S₀)∖{P({m+1})} corresponds to a set cover in C. Therefore, |T∩S₀|≥k+1. Similarly, for any 0≤j≤m, |T∩S_j|≥k+1. Therefore, |T|≥(k+1)(m+1). End of proof sketch of Claim.

Let n=2m+2. For E⊆[m+1], let P_E be the n×n permutation matrix which is block diagonal with n 2×2 blocks so that ith block is $\pmatrix{0 & 1 \\ 1 & 0}$ if i∈E and $\pmatrix{1 & 0 \\ 0 & 1}$ otherwise. Let Q be the n×n permutation matrix whose (i, i+2)-entry is 1 for all 1≤i≤n (where the index i+2 are interpreted as modulo n). For 0≤j≤m, define S_j = {P_EQ^j: E∈C∪{{m+1}}} and S = S₀∪…∪S_m.

Proof sketch. If D⊆C is a cover of [m], we can construct a cover T⊆S of size (|D|+1)(m+1) by T = {P_EQ^j: E∈S∪{{m+1}}, 0≤j≤m}.

On the other hand, let T⊆S be a cover. Note that all the matrices in S₀ are block diagonal with blocks of size 2×2, and the other matrices in S have 0 in these blocks. Therefore, T∩S₀ covers these blocks. Moreover, T∩S₀ contains P_{m+1} since otherwise the (2m+1, 2m+2)-entry would not be covered. Observe that (T∩S₀)∖{P_{m+1}} corresponds to a set cover in C. Therefore, |T∩S₀|≥k+1. Similarly, for any 0≤j≤m, |T∩S_j|≥k+1. Therefore, |T|≥(k+1)(m+1). End of proof sketch of Claim.