Définir la couverture pour les matrices de permutation

16

Étant donné un ensemble S de matrices de permutation nxn (qui n'est qu'une petite fraction des n! Matrices de permutation possibles), comment pouvons-nous trouver des sous-ensembles de taille minimale T de S tels que l'ajout des matrices de T a au moins 1 dans chaque position?

Je suis intéressé par ce problème où S est un petit sous-groupe de S_n. Je me demande s'il est possible de trouver (et de mettre en œuvre!) Des algorithmes d'approximation beaucoup plus rapides que les algorithmes gourmands (exécutés plusieurs fois jusqu'à ce qu'il soit `` chanceux '', ce qui est une procédure très lente mais néanmoins il a donné des limites presque optimales dans de petits cas), ou si l'inapproximabilité garantit que je ne peux pas.

Quelques faits simples sur ce problème: Un groupe cyclique de longueur n de matrices de permutation résout ce problème, bien sûr de manière optimale. (Au moins n matrices sont nécessaires car chaque matrice de permutation en a n et il en faut n ^ 2.)

Les ensembles S qui m'intéressent n'ont pas de groupe n-cyclique en eux.

Ce problème est un cas très spécial de couvre-ensemble. En effet, si nous laissons X être l'ensemble (1,2, ... n) * (1,2, ... n), avec n ^ 2 éléments, alors chaque matrice de permutation correspond à un sous-ensemble de taille n, et I suis à la recherche de la plus petite sous-collection de ces sous-ensembles qui couvrent X. La couverture d'ensemble elle-même n'est pas un bon moyen d'examiner ce problème, car l'approximation du problème général de couverture d'ensemble.

La seule raison pour laquelle ce problème n'est pas beaucoup trop lent en utilisant l'approche gourmande est que la symétrie dans le groupe de permutation aide à éliminer beaucoup de redondance. En particulier, si S est un sous-groupe, et T est un petit sous-ensemble qui est un ensemble de couverture minimal, alors les ensembles sT (multiplier T par n'importe quel élément du groupe s) sont toujours dans S et sont toujours un ensemble de couverture (bien sûr de la même taille, donc toujours minime.) Au cas où vous vous poseriez la question, le cas réussi a n ~ 30 et | S | ~ 1000, avec des résultats gourmands chanceux ayant | T | ~ 37. Les cas avec n ~ 50 ont des limites très médiocres qui prennent beaucoup de temps à obtenir.

Pour résumer, je me demande s'il existe des approches d'approximation à ce problème ou s'il est encore suffisamment général pour s'inscrire dans un théorème d'inapproximabilité, comme il y en a pour le problème général de la couverture d'ensemble. Quels algorithmes sont utilisés pour rapprocher les problèmes connexes dans la pratique? Il semble qu'il puisse y avoir quelque chose de possible car les sous-ensembles sont tous de la même taille et chaque élément apparaît à la même petite fréquence 1 / n.

-B

Brayden Ware
la source
voulez-vous vraiment ajouter? Je suppose que vous voulez dire plutôt une sorte d '«union», ou vraiment un OU? car sinon vous pourriez vous retrouver avec un 2 dans une entrée.
Suresh Venkat
L'union fonctionne bien. Si j'ajoute, je dois obtenir «au moins» 1 dans chaque entrée. La raison pour laquelle je l'imagine comme addition est parce que je suis vraiment un mathématicien, et il y a toujours une signification mathématique dans l'ajout d'éléments de groupe (cela ne dépend pas du groupe représenté comme matrices de permutation) mais pas dans la `` réunion '' des matrices.
Brayden Ware,
Mais il n'y a aucun moyen utile d'énoncer cette condition sans les matrices de permutation, alors n'hésitez pas à penser à l'union. Les 2 (et Dieu ne plaise pas 3 ou plus) ne serviraient que de marqueurs que nous ne sommes pas dans la solution de rêve d'exactement n matrices ajoutant à la matrice des 1, le nombre de 2 et plus mesurant le nombre de matrices supplémentaires que nous avons utilisées. (Chaque matrice supplémentaire ajoute n à la somme totale à la fin.)
Brayden Ware

Réponses:

10

Voici une analyse presque étroite de l'approximation pour le cas où S n'est pas tenu d'être un sous-groupe du groupe symétrique.

Ce problème est un cas particulier de Set Cover, et il existe un algorithme d'approximation gourmand simple [Joh74]. Si nous notons le k ème nombre harmonique comme H k = ∑ i = 1 k 1 / i , l'algorithme gourmand atteint un rapport d'approximation H n = ln n + Θ (1). (Il y a un algorithme [DF97] qui se traduit par un rapport d'approximation légèrement meilleure H n -1/2). ( Edition : Révision 2 et précédemment indiqué le rapport d'approximation de l'algorithme glouton pire que la valeur correcte.)

De plus, c'est presque optimal dans le sens suivant:

Théorème . La couverture d'ensemble pour les matrices de permutation ne peut pas être approximée dans un rapport d'approximation (1− ε ) ln n pour toute constante 0 < ε <1 sauf si NP ⊆ DTIME ( n O (log log n ) ).

Voici un croquis d'une preuve. Nous écrivons [ n ] = {1,…, n }. Nous allons construire une réduction à partir de Set Cover:

Set Cover
Instance : Un entier positif m et une collection C de sous-ensembles de [ m ].
Solution : Un sous-ensemble D de C tel que l'union des ensembles dans D soit égale à [ m ].
Objectif : minimiser | D |.

C'est un résultat célèbre de Feige [Fei98] que Set Cover ne peut pas être approximé dans un rapport d'approximation (1− ε ) ln m pour toute constante 0 < ε <1 sauf NP ⊆ DTIME ( n O (log log n ) ).

Soit ( m , C ) une instance de Set Cover. Nous allons construire une instance ( n , S ) de Set Cover for Permutation Matrices.

(0110)(1001)in (où l'indice i +2 est interprété comme modulo n ). Pour 0≤ jm , définissez S j = { P E Q j : EC ∪ {{ m +1}}} et S = S 0 ∪… ∪ S m .

Réclamation . Que k soit la taille de la couverture minimum de [ m ] en C . Alors la taille de couverture minimale en S est égale à ( k +1) ( m +1).

Croquis de preuve . Si DC est une couverture de [ m ], on peut construire une couverture TS de taille (| D | +1) ( m +1) par T = { P E Q j : ES ∪ {{ m +1}}, 0≤ jm }.

Par contre, que TS soit une couverture. Notez que toutes les matrices dans S 0 sont des blocs en diagonale avec des blocs de taille 2 × 2, et les autres matrices dans S ont 0 dans ces blocs. Par conséquent, TS 0 couvre ces blocs. De plus, TS 0 contient P { m +1} car sinon l' entrée (2 m +1, 2 m +2) ne serait pas couverte. Observez que ( TS 0 ) ∖ { P { m +1}} Correspond à une couverture de l' ensemble en C . Par conséquent, | TS 0 | ≥ k +1. De même, pour tout 0≤ jm , | TS j | ≥ k +1. Par conséquent, | T | ≥ ( k +1) ( m +1). Croquis de fin de preuve de la réclamation .

Selon la revendication, la réduction construite ci-dessus préserve le rapport d'approximation. En particulier, il établit le théorème.

Les références

[DF97] Rong-Chii Duh et Martin Fürer. Approximation de la couverture k- set par optimisation semi-locale. Dans Actes du vingt-neuvième symposium annuel de l'ACM sur la théorie de l'informatique (STOC) , pp. 256-264, mai 1997. http://dx.doi.org/10.1145/258533.258599

[Fei98] Uriel Feige. Un seuil de ln n pour approximer la couverture d'ensemble. Journal de l'ACM , 45 (4): 634–652, juillet 1998. http://dx.doi.org/10.1145/285055.285059

[Joh74] David S. Johnson. Algorithmes d'approximation pour les problèmes combinatoires. Journal of Computer and System Sciences , 9 (3): 256-278, décembre 1974. http://dx.doi.org/10.1016/S0022-0000(74)80044-9

Tsuyoshi Ito
la source
3
Tsuyoshi, vos réponses ont été assez impressionnantes ces derniers temps. Un jour, l'une de vos preuves sur ce site sera citée sous le nom de Ito Lemma. :-)
Aaron Sterling
@Aaron: Merci pour votre aimable commentaire. Notez que la chose la plus difficile de la question, à savoir la restriction au cas d'un sous-groupe, est totalement ignorée dans cette réponse. Il est temps de réfléchir!
Tsuyoshi Ito
3
@Aaron: Je ne sais pas si vous avez dit cela intentionnellement, mais le lemme d'Ito est pris ( en.wikipedia.org/wiki/Ito_lemma ).
Robin Kothari
11

Au cours du déjeuner à Bruxelles, nous avons prouvé que ce problème est NP-difficile par une réduction assez courte de 3SAT. Notre preuve ne conduit pas (encore) à un résultat d'inapproximabilité. Nous y réfléchirons davantage.

En gros, vous transformez une instance 3-SAT (avec n variables et clauses c) en une série de permutations structurées comme suit:

1 ... n pour numéroter les n variables n + 1 utilisées par le gadget variable n + 2, n + 3 représentant la 1ère clause ... n + 2j, n + 2j + 1 représentant la jième clause n + 2c + 2 utilisé par le garbage collector

la variable xi est représentée par la permutation 1, ..., i-1, n + 1, i + 1, ..., n, i, ... et l'échange de n + 2j + 1, n + 2j pour chaque clause où j où xi apparaît; et la permutation 1, ..., i-1, n + 1, i + 1, ..., n, i, ... et l'échange de n + 2j + 1, n + 2j pour chaque clause où j où - xi apparaît.

Ensuite, nous utilisons le garbage collector pour placer chaque numéro dans une position où il ne pourrait pas apparaître autrement. Pour placer x en position y, on met y en position n + 2c + 2 et n + 2c + 2 en position x. Nous aurons exactement n + 2c-1 de tels récupérateurs pour chaque variable et 2 (n + 2c-1) pour chaque clause. La 3SAT est satisfiable si nous pouvons choisir exactement l'une des 2 permutations pour chaque variable, si la couverture de l'ensemble de permutation a une solution de taille n + (n + 2c-1) (n + 2c).

Il y a probablement quelques détails mineurs manquants pour les petites instances.

Stefan.

Stefan Langerman
la source