Dado um conjunto S de nxn matrizes de permutação (que é apenas uma pequena fração das n! Possíveis matrizes de permutação), como podemos encontrar subconjuntos de tamanho mínimo T de S de modo que a adição de matrizes de T tenha pelo menos 1 em todas as posições?
Estou interessado neste problema em que S é um pequeno subgrupo de S_n. Eu estou querendo saber se é possível encontrar (e implementar!) Algoritmos de aproximação que são muito mais rápidos do que os algoritmos gananciosos (executados muitas vezes até que tenha sorte), que é um procedimento muito lento, mas mesmo assim deu alguns limites quase ideais em casos pequenos) ou se a inadequação garante que eu não posso.
Alguns fatos fáceis sobre esse problema: Um grupo cíclico de n de matrizes de permutação resolve esse problema, é claro, de maneira ideal. (São necessárias pelo menos n matrizes porque cada matriz de permutação possui n e há n ^ 2 necessárias.)
Os conjuntos S dos quais estou interessado não possuem um grupo n-cíclico.
Esse problema é um caso muito especial de cobertura do conjunto. De fato, se deixarmos X ser o conjunto (1,2, ... n) * (1,2, ... n), com n ^ 2 elementos, cada matriz de permutação corresponderá a um subconjunto de tamanho n, e I estou procurando a menor subcoleção desses subconjuntos que cobrem o X. A cobertura do conjunto em si não é uma boa maneira de analisar esse problema, porque a aproximação do problema geral de cobertura do conjunto.
A única razão pela qual esse problema não é muito lento usando a abordagem gananciosa é porque a simetria no grupo de permutação ajuda a eliminar muita redundância. Em particular, se S é um subgrupo e T é um pequeno subconjunto que é um conjunto mínimo de cobertura, então os conjuntos sT (multiplique T por qualquer elemento do grupo s) ainda estão em S e ainda são um conjunto de cobertura (é claro do mesmo tamanho, ainda assim mínimo.) Caso você esteja se perguntando, o caso de sucesso tem n ~ 30 e | S | ~ 1000, com resultados gananciosos da sorte tendo | T | ~ 37. Casos com n ~ 50 têm limites muito ruins, levando muito tempo para serem alcançados.
Para resumir, estou me perguntando se existem abordagens de aproximação para esse problema ou se ainda é geral o suficiente para caber dentro de algum teorema de inadequação - como existe para o problema geral de cobertura do conjunto. Quais algoritmos são usados para aproximar problemas relacionados na prática? Parece que pode haver algo possível, pois os subconjuntos têm o mesmo tamanho e todos os elementos aparecem na mesma pequena frequência 1 / n.
-B
fonte
Respostas:
Aqui está uma análise quase aproximada da aproximabilidade para o caso em que não é necessário que S seja um subgrupo do grupo simétrico.
Esse problema é um caso especial do Set Cover, e existe um algoritmo de aproximação simples e ganancioso [Joh74]. Se denotar o k th número harmónico como H k = Σ i = 1 k 1 / i , o algoritmo ávido atinge uma relação de aproximação H n = ln n + Θ (1). (Existe um algoritmo [DF97] que resulta em uma taxa de aproximação um pouco melhor H n −1/2.) ( Edit : Revisão 2 e anterior declararam que a taxa de aproximação do algoritmo ganancioso é pior que o valor correto.)
Além disso, isso é quase ideal no seguinte sentido:
Teorema . A tampa de ajuste para matrizes de permutação não pode ser aproximada dentro de uma taxa de aproximação (1− ε ) ln n para qualquer constante 0 < ε <1, a menos que NP ⊆ DTIME ( n O (log log n ) ).
Aqui está um esboço de uma prova. Escrevemos [ n ] = {1,…, n }. Construiremos uma redução do Set Cover:
Conjunto de tampa
Instância : Um número inteiro positivo m e um conjunto C de subconjuntos de [ m ].
Solução : um subconjunto D de C de modo que a união dos conjuntos em D seja igual a [ m ].
Objetivo : Minimizar | D |.
É um resultado famoso de Feige [Fei98] que Set Cover não pode ser aproximado dentro de uma taxa de aproximação (1− ε ) ln m para qualquer constante 0 < ε <1, a menos que NP ⊆ DTIME ( n O (log log n ) ).
Seja ( m , C ) uma instância do Set Cover. Construiremos uma instância ( n , S ) de Set Cover for Permutation Matrizes.
Reivindicação . Deixe- k ter o tamanho de cobertura mínima de [ m ] em C . Então o tamanho da cobertura mínima em S é igual a ( k +1) ( m +1).
Esboço de prova . Se D ⊆ C é uma cobertura de [ m ], podemos construir uma cobertura T ⊆ S de tamanho (| D | +1) ( m +1) por T = { P E Q j : E ∈ S ∪ {{ m +1}}, 0≤ j ≤ m }.
Por outro lado, deixe T ⊆ S ser uma cobertura. Observe que todas as matrizes em S 0 são diagonais de bloco com blocos de tamanho 2 × 2, e as outras matrizes em S têm 0 nesses blocos. Portanto, T ∩ S 0 cobre esses blocos. Além disso, T ∩ S 0 contém P { m +1}, pois, caso contrário, a entrada (2 m +1, 2 m +2) não seria coberta. Observe que ( T ∩ S 0 ) ∖ { P { m +1}} Corresponde a uma cobertura em conjunto C . Portanto, | T ∩ S 0 | ≥ k +1. Da mesma forma, para qualquer 0≤ j ≤ m , | T ∩ S j | ≥ k +1. Portanto, | T | ≥ ( k +1) ( m +1). Esboço de final de prova da reivindicação .
Por reivindicação, a redução construída acima preserva a taxa de aproximação. Em particular, estabelece o teorema.
Referências
[DF97] Rong-Chii Duh e Martin Fürer. Aproximação da cobertura do conjunto k por otimização semi-local. Em Anais do Vigésimo Nono Simpósio Anual da ACM sobre Teoria da Computação (STOC) , pp. 256–264, maio de 1997. http://dx.doi.org/10.1145/258533.258599
Uriel Feige. Um limite de ln n para aproximar a cobertura do conjunto. Journal of the ACM , 45 (4): 634–652, julho de 1998. http://dx.doi.org/10.1145/285055.285059
David S. Johnson. Algoritmos de aproximação para problemas combinatórios. Journal of Computer and System Sciences , 9 (3): 256–278, dezembro de 1974. http://dx.doi.org/10.1016/S0022-0000(74)80044-9
fonte
Durante o almoço em Bruxelas, provamos que esse problema é NP-Hard, com uma redução relativamente curta da 3SAT. Nossa prova ainda não leva a um resultado de inadequação. Vamos pensar mais sobre isso.
Grosso modo, você transforma uma instância 3-SAT (com n variáveis e cláusulas c) em uma série de permutações estruturadas da seguinte maneira:
1 ... n para numerar as n variáveis n + 1 usadas pelo dispositivo variável n + 2, n + 3 representando a 1ª cláusula ... n + 2j, n + 2j + 1 representando a j-ésima cláusula n + 2c + 2 usado pelo coletor de lixo
A variável xi é representada pela permutação 1, ..., i-1, n + 1, i + 1, ..., n, i, ... e trocando n + 2j + 1, n + 2j para cada cláusula onde j onde xi aparece; e a permutação 1, ..., i-1, n + 1, i + 1, ..., n, i, ... e trocando n + 2j + 1, n + 2j para cada cláusula em que j onde - xi aparece.
Em seguida, usamos o coletor de lixo para colocar cada número em uma posição em que não possa aparecer de outra forma. Para colocar x na posição y, colocamos y na posição n + 2c + 2 en + 2c + 2 na posição x. Teremos exatamente n + 2c-1 desses coletores de lixo para cada variável e 2 (n + 2c-1) para cada cláusula. O 3SAT é satisfatório se pudermos escolher exatamente uma das 2 permutações para cada variável, se a tampa do conjunto de permutações tiver uma solução do tamanho n + (n + 2c-1) (n + 2c).
Provavelmente existem alguns detalhes menores ausentes para pequenas instâncias.
Stefan.
fonte