16
$\begingroup$

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

$\endgroup$
  • $\begingroup$ do you really mean adding ? I assume you mean instead a kind of 'union', or really an ORing ? because otherwise you might end up with a 2 in an entry. $\endgroup$ – Suresh Venkat Nov 12 '10 at 6:27
  • $\begingroup$ Unioning works fine. If I add, then I need to get 'at least' 1 in every entry. The reason why I imagine it as adding is because really I am a mathematician, and there is still mathematical meaning in adding group elements (that does not depend on the group being represented as permutation matrices) but not in 'unioning' the matrices. $\endgroup$ – Brayden Ware Nov 12 '10 at 6:50
  • $\begingroup$ But there isn't any useful way of stating this condition without the permutation matrices so feel free to think of unioning. 2s (and god forbid 3s or more) would serve only as markers that we are not in the dream solution of exactly n matrices adding to the all 1s matrix, the number of 2s and higher measuring just how many extra matrices we used. (Each extra matrix adds n to the total sum in the end.) $\endgroup$ – Brayden Ware Nov 12 '10 at 6:55
10
$\begingroup$

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 Hk = ∑i=1k 1/i, the greedy algorithm achieves an approximation ratio Hn = ln n + Θ(1). (There is an algorithm [DF97] which results in a slightly better approximation ratio Hn−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(nO(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(nO(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 PE 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 iE 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≤in (where the index i+2 are interpreted as modulo n). For 0≤jm, define Sj = {PEQj: EC∪{{m+1}}} and S = S0∪…∪Sm.

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 DC is a cover of [m], we can construct a cover TS of size (|D|+1)(m+1) by T = {PEQj: ES∪{{m+1}}, 0≤jm}.

On the other hand, let TS be a cover. Note that all the matrices in S0 are block diagonal with blocks of size 2×2, and the other matrices in S have 0 in these blocks. Therefore, TS0 covers these blocks. Moreover, TS0 contains P{m+1} since otherwise the (2m+1, 2m+2)-entry would not be covered. Observe that (TS0)∖{P{m+1}} corresponds to a set cover in C. Therefore, |TS0|≥k+1. Similarly, for any 0≤jm, |TSj|≥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

$\endgroup$
  • 3
    $\begingroup$ Tsuyoshi, your answers lately have been quite impressive. Someday, one of your proofs on this site will be cited as the Ito Lemma. :-) $\endgroup$ – Aaron Sterling Nov 14 '10 at 22:00
  • $\begingroup$ @Aaron: Thanks for your kind comment. Note that the most difficult thing in the question, namely the restriction to the case of a subgroup, is totally ignored in this answer. It’s time to think! $\endgroup$ – Tsuyoshi Ito Nov 14 '10 at 22:23
  • 3
    $\begingroup$ @Aaron: I don't know if you said that intentionally, but Ito's lemma is taken (en.wikipedia.org/wiki/Ito_lemma). $\endgroup$ – Robin Kothari Nov 14 '10 at 22:55
11
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.