<p>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.</p>

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

<p>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</p>

<p>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.</p>

<p>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).</p>

<p>There are probably some minor details missing for small instances.</p>

<p>Stefan.</p>

CC BY-SA 2.5
2010-11-13T06:46:51.300Z
2010-11-13T06:46:51.300Z
Stefan Langerman
<p>Here is an almost tight analysis of approximability for the case where <i>S</i> is <em>not</em> required to be a subgroup of the symmetric group.</p>

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

<p>Moreover, this is almost optimal in the following sense:</p>

<p><strong>Theorem</strong>.  Set Cover for Permutation Matrices cannot be approximated within an approximation ratio (1−<i>ε</i>) ln <i>n</i> for any constant 0&lt;<i>ε</i>&lt;1 unless NP ⊆ DTIME(<i>n</i><sup>O(log log <i>n</i>)</sup>).</p>

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

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

<p>It is a famous result by Feige [Fei98] that Set Cover cannot be approximated within an approximation ratio (1−<i>ε</i>) ln <i>m</i> for any constant 0&lt;<i>ε</i>&lt;1 unless NP ⊆ DTIME(<i>n</i><sup>O(log log <i>n</i>)</sup>).</p>

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

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

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

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

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

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

<p>References</p>

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

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

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

CC BY-SA 2.5
2010-11-14T22:00:15.300Z
Tsuyoshi, your answers lately have been quite impressive.  Someday, one of your proofs on this site will be cited as the Ito Lemma. :-)
Aaron Sterling
CC BY-SA 2.5
2010-11-14T22:23:06.520Z
@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!
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-14T22:55:50.083Z
@Aaron: I don't know if you said that intentionally, but Ito's lemma is taken (http://en.wikipedia.org/wiki/Ito_lemma).
Robin Kothari
CC BY-SA 2.5
2010-11-14T21:43:04.823Z
2010-11-15T05:12:39.453Z
2010-11-15T05:12:39.453Z
Tsuyoshi Ito
<p>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?</p>

<p>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. </p>

<p>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.)</p>

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

<p>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.</p>

<p>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. </p>

<p>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. </p>

<p>-B</p>

CC BY-SA 2.5
2010-11-12T06:27:11.947Z
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.
Suresh Venkat
CC BY-SA 2.5
2010-11-12T06:50:32.550Z
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.
Brayden Ware
CC BY-SA 2.5
2010-11-12T06:55:39.940Z
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.)
Brayden Ware
<ds.algorithms><approximation-algorithms><set-cover><permutations>
Set Cover for Permutation Matrices
Brayden Ware
# Set Cover for Permutation Matrices

(Asked by: username_0 on 2010-11-12)

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

**Tags:** ds.algorithms, approximation-algorithms, set-cover, permutations
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: 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.)  

---

## 2 answers

### Answer by username_3 on 2010-11-14. Score: 10 | Accepted answer

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 *k*th 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*=2*m*+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 *i*th 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*0∪…∪*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**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*0 are block diagonal with blocks of size 2×2, and the other matrices in *S* have 0 in these blocks. Therefore, *T*∩*S*0 covers these blocks. Moreover, *T*∩*S*0 contains *P*{*m*+1} since otherwise the (2*m*+1, 2*m*+2)-entry would not be covered. Observe that (*T*∩*S*0)∖{*P*{*m*+1}} corresponds to a set cover in *C*. Therefore, |*T*∩*S*0|≥*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>

> **Comments:**
> **username_4**: Tsuyoshi, your answers lately have been quite impressive.  Someday, one of your proofs on this site will be cited as the Ito Lemma. :-)  
> **username_3**: @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!  
> **username_5**: @Aaron: I don't know if you said that intentionally, but Ito's lemma is taken (http://en.wikipedia.org/wiki/Ito_lemma).  

---

### Answer by username_2 on 2010-11-13. Score: 11

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.


---

