Establecer cubierta para matrices de permutación

Dado un conjunto S de matrices de permutación nxn (que es solo una pequeña fracción de las n! Matrices de permutación posibles), ¿cómo podemos encontrar subconjuntos T de tamaño mínimo de S de manera que sumar las matrices de T tenga al menos 1 en cada posición?

Estoy interesado en este problema donde S es un pequeño subgrupo de S_n. Me pregunto si es posible encontrar (¡e implementar!) Algoritmos de aproximación que sean mucho más rápidos que los codiciosos algoritmos (se ejecutan muchas veces hasta que tuvo 'suerte', que es un procedimiento muy lento pero que, sin embargo, ha dado algunos límites casi óptimos en casos pequeños), o si la imposibilidad de aproximación garantiza que no puedo.

Algunos datos fáciles sobre este problema: un grupo de matrices de permutación de longitud n cíclica resuelve este problema, por supuesto de manera óptima. (Se necesitan al menos n matrices porque cada matriz de permutación tiene n unas y se necesitan n ^ 2 unas).

Los conjuntos S que me interesan no tienen un grupo n-cíclico en ellos.

Este problema es un caso muy especial de cubierta de conjunto. De hecho, si dejamos que X sea el conjunto (1,2, ... n) * (1,2, ... n), con n ^ 2 elementos, entonces cada matriz de permutación corresponde a un subconjunto de tamaño n, y yo Estoy buscando la subcolección más pequeña de estos subconjuntos que cubren X. La cubierta del conjunto en sí no es una buena manera de ver este problema, porque la aproximación del problema general de la cubierta del conjunto.

La única razón por la cual este problema no es demasiado lento utilizando el enfoque codicioso es porque la simetría en el grupo de permutación ayuda a eliminar mucha redundancia. En particular, si S es un subgrupo y T es un pequeño subconjunto que es un conjunto de cobertura mínimo, entonces los conjuntos sT (multiplique T por cualquier elemento del grupo s) todavía están en S y siguen siendo un conjunto de cobertura (por supuesto del mismo tamaño, por lo que sigue siendo mínimo.) En caso de que se lo pregunte, el caso exitoso tiene n ~ 30 y | S | ~ 1000, con resultados afortunados y codiciosos que tienen | T | ~ 37. Los casos con n ~ 50 tienen algunos límites muy pobres que tardan mucho tiempo en llegar.

Para resumir, me pregunto si hay enfoques de aproximación a este problema o si todavía es lo suficientemente general como para ajustarse a algún teorema de inaproximabilidad, como el que existe para el problema general de la cobertura del conjunto. ¿Qué algoritmos se utilizan para aproximar problemas relacionados en la práctica? Parece que puede haber algo posible ya que los subconjuntos son todos del mismo tamaño y cada elemento aparece en la misma pequeña frecuencia 1 / n.

-SI

Aquí hay un análisis casi estricto de la aproximabilidad para el caso en el que no se requiere que S sea ​​un subgrupo del grupo simétrico.

Este problema es un caso especial de Set Cover, y hay un algoritmo de aproximación codicioso simple [Joh74]. Si denotamos el número k armónico como H _k = ∑ _{i = 1} ^k 1 / i , el algoritmo codicioso logra una relación de aproximación H _n = ln n + Θ (1). (Existe un algoritmo [DF97] que da como resultado una relación de aproximación ligeramente mejor H _n −1/2.) ( Editar : Revisión 2 y anterior estableció la relación de aproximación del algoritmo codicioso peor que el valor correcto).

Además, esto es casi óptimo en el siguiente sentido:

Teorema . Establecer la cobertura para las matrices de permutación no puede aproximarse dentro de una relación de aproximación (1− ε ) ln n para cualquier constante 0 < ε <1 a menos que NP ⊆ DTIME ( n ^{O (log log n )} ).

Aquí hay un boceto de una prueba. Escribimos [ n ] = {1, ..., n }. Construiremos una reducción de Set Cover:

Establecer
instancia de portada : un entero positivo my una colección C de subconjuntos de [ m ].
Solución : Un subconjunto D de C tal que la unión de los conjuntos en D sea ​​igual a [ m ].
Objetivo : minimizar | D |.

Es un resultado famoso de Feige [Fei98] que Set Cover no puede aproximarse dentro de una relación de aproximación (1− ε ) ln m para cualquier constante 0 < ε <1 a menos que NP ⊆ DTIME ( n ^{O (log log n )} ).

Sea ( m , C ) una instancia de Set Cover. Construiremos una instancia ( n , S ) de Set Cover para matrices de permutación.

$\pmatrix{0 & 1 \\ 1 & 0}$$\pmatrix{1 & 0 \\ 0 & 1}$i ≤ n (donde el índice i +2 se interpreta como módulo n ). Para 0≤ j ≤ m , defina S _j = { P _E Q ^j : E ∈ C ∪ {{ m +1}}} y S = S ₀ ∪… ∪ S _m .

Reclamo . Deje que k sea el tamaño de cobertura mínima de [ m ] en C . Entonces el tamaño de la cobertura mínima en S es igual a ( k +1) ( m +1).

Bosquejo de prueba . Si D ⊆ C es una cubierta de [ m ], podemos construir una cubierta T ⊆ S de tamaño (| D | +1) ( m +1) por T = { P _E Q ^j : E ∈ S ∪ {{ m +1}}, 0≤ j ≤ m }.

Por otro lado, deja que T ⊆ S sea ​​una tapadera. Tenga en cuenta que todas las matrices en S ₀ son diagonales de bloque con bloques de tamaño 2 × 2, y las otras matrices en S tienen 0 en estos bloques. Por lo tanto, T ∩ S ₀ cubre estos bloques. Además, T ∩ S ₀ contiene P _{{ m +1}} ya que de lo contrario la entrada (2 m +1, 2 m +2) no estaría cubierta. Observe que ( T ∩ S ₀ ) ∖ { P _{{ m +1}}} Corresponde a una cubierta de conjunto en C . Por lo tanto | T ∩ S ₀ | ≥ k +1. Del mismo modo, para cualquier 0≤ j ≤ m , | T ∩ S _j | ≥ k +1. Por lo tanto | T | ≥ ( k +1) ( m +1). Fin del boceto de prueba de Reclamación .

Por Reclamación, la reducción construida anteriormente conserva la relación de aproximación. En particular, establece el teorema.

Referencias

[DF97] Rong-Chii Duh y Martin Fürer. Aproximación de la cubierta k- set por optimización semi-local. En Actas del Vigésimo Noveno Simposio Anual de ACM sobre Teoría de la Computación (STOC) , pp. 256–264, mayo de 1997. http://dx.doi.org/10.1145/258533.258599

[Fei98] Uriel Feige. Un umbral de ln n para aproximar la cobertura del conjunto. Journal of the ACM , 45 (4): 634–652, julio de 1998. http://dx.doi.org/10.1145/285055.285059

[Joh74] David S. Johnson. algoritmos de aproximación para problemas combinatorios. Journal of Computer and System Sciences , 9 (3): 256–278, diciembre de 1974. http://dx.doi.org/10.1016/S0022-0000(74)80044-9

Durante el almuerzo en Bruselas, demostramos que este problema es NP-Hard por una reducción bastante corta de 3SAT. Nuestra prueba no conduce a un resultado de inaccesibilidad (todavía). Lo pensaremos más.

Aproximadamente, transforma una instancia de 3-SAT (con n variables y c cláusulas) en una serie de permutaciones estructuradas de la siguiente manera:

1 ... n para numerar las n variables n + 1 utilizadas por el gadget variable n + 2, n + 3 representando la primera cláusula ... n + 2j, n + 2j + 1 representando la cláusula jth n + 2c + 2 utilizado por el recolector de basura

La variable xi está representada por la permutación 1, ..., i-1, n + 1, i + 1, ..., n, i, ... e intercambiando n + 2j + 1, n + 2j por cada cláusula donde j donde aparece xi; y la permutación 1, ..., i-1, n + 1, i + 1, ..., n, i, ... e intercambiando n + 2j + 1, n + 2j por cada cláusula donde j donde - xi aparece.

Luego usamos el recolector de basura para colocar cada número en una posición donde no podría aparecer de otra manera. Para colocar x en la posición y, colocamos y en la posición n + 2c + 2 yn + 2c + 2 en la posición x. Tendremos exactamente n + 2c-1 tales recolectores de basura para cada variable y 2 (n + 2c-1) para cada cláusula. El 3SAT es satisfactoria si podemos elegir exactamente una de las 2 permutaciones para cada variable, si la cubierta del conjunto de permutación tiene una solución de tamaño n + (n + 2c-1) (n + 2c).

Probablemente faltan algunos detalles menores para instancias pequeñas.

Stefan