Set Cover for Permutation Matrices

Question

Given a set S of nxn permutation matrices (which is only a small fraction of the n! possible permutation matrices), how can we find minimal-size subsets T of S such that adding the matrices of T has at least 1 in every position?

I am interested in this problem where S is a small subgroup of S_n. I am wondering whether it is possible to find (and implement!) approximation algorithms that are much quicker than the greedy algorithms (run many times until it got 'lucky', which is a very slow procedure but nonetheless it has given some near optimal bounds in small cases), or whether inapproximability guarantees that I cannot.

A few easy facts about this problem: A length n cyclic group of permutation matrices solves this problem, of course optimally. (At least n matrices are needed because each permutation matrix has n ones and there are n^2 ones needed.)

The sets S of which I am interested do not have a n-cyclic group in them.

This problem is a very special case of set cover. Indeed, if we let X be the set (1,2, ... n)*(1,2,... n), with n^2 elements, then each permutation matrix corresponds to a size n subset, and I'm looking for the smallest subcollection of these subsets that cover X. Set cover itself is not a good way to look at this problem, because approximation of the general set cover problem.

The only reason why this problem is not much too slow using the greedy approach is because symmetry in the permutation group helps eliminate a lot of redundancy. In particular, if S is a subgroup, and T is a small subset which is a minimal covering set, then the sets sT (multiply T by any element of the group s) are still in S and still are a covering set (of course of the same size, so still minimal.) In case you were wondering, the successful case has n~30 and |S|~1000, with lucky greedy results having |T| ~37. Cases with n~50 have some very poor bounds taking a very long time to get.

To summarize, I am wondering if there are approximation approaches to this problem or if it is still general enough to fit within some inapproximability theorem- like there is for the general set cover problem. What algorithms are used to approximate related problems in practice? It seems like there may be something possible since the subsets are all of the same size and every element appears at the same small frequency 1/n.

-B

Answer 1

Here is an almost tight analysis of approximability for the case where S is not required to be a subgroup of the symmetric group.

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:

Theorem. Set Cover for Permutation Matrices cannot be approximated within an approximation ratio (1−ε) ln n for any constant 0<ε<1 unless NP ⊆ DTIME(n^{O(log log n)}).

Here is a sketch of a proof. We write [n] = {1, …, n}. We will construct a reduction from Set Cover:

Set Cover
Instance: A positive integer m and a collection C of subsets of [m].
Solution: A subset D of C such that the union of the sets in D is equal to [m].
Objective: Minimize |D|.

It is a famous result by Feige [Fei98] that Set Cover cannot be approximated within an approximation ratio (1−ε) ln m for any constant 0<ε<1 unless NP ⊆ DTIME(n^{O(log log n)}).

Let (m, C) be an instance of Set Cover. We will construct an instance (n, S) of Set Cover for Permutation Matrices.

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.

Claim. Let k be the size of minimum cover of [m] in C. Then the size of minimum cover in S is equal to (k+1)(m+1).

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.

By Claim, the reduction constructed above preserves the approximation ratio. In particular, it establishes the theorem.

References

[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

Answer 2

Over lunch in Brussels we proved this problem is NP-Hard by a fairly short reduction from 3SAT. Our proof doesn't lead to an inapproximability result (yet). We'll think more about it.

Roughly, you transform a 3-SAT instance (with n variables and c clauses) into a series of permutations structured as follows:

1...n for numbering the n variables n+1 used by the variable gadget n+2, n+3 representing the 1st clause ... n+2j, n+2j+1 representing the jth clause n+2c+2 used by the garbage collector

variable xi is represented by the permutation 1,...,i-1,n+1,i+1,...,n,i,... and swapping n+2j+1, n+2j for every clause where j where xi appears; and the permutation 1,...,i-1,n+1,i+1,...,n,i,... and swapping n+2j+1, n+2j for every clause where j where -xi appears.

Then we use the garbage collector to place each number in a position where it could not appear otherwise. To place x in position y, we put y in position n+2c+2 and n+2c+2 in position x. We will have exactly n+2c-1 such garbage collectors for each variable and 2(n+2c-1) for each clause. The 3SAT is satisfiable iff we can choose exactly one of the 2 permutations for each variable, iff the permutation set cover has a solution of size n+(n+2c-1)(n+2c).

There are probably some minor details missing for small instances.

Stefan.