Definir cobertura para matrizes de permutação

16

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

Brayden Ware
fonte
você realmente quer dizer adicionar? Suponho que você queira dizer uma espécie de 'união', ou realmente um ORing? porque, caso contrário, você pode acabar com um 2 em uma entrada.
Suresh Venkat
A união funciona bem. Se eu adicionar, preciso obter 'pelo menos' 1 em cada entrada. A razão pela qual eu imagino que adicionando é porque realmente sou um matemático, e ainda há significado matemático na adição de elementos de grupo (que não depende do grupo ser representado como matrizes de permutação), mas não em 'união' das matrizes.
Brayden Ware
Mas não há nenhuma maneira útil de declarar essa condição sem as matrizes de permutação, portanto fique à vontade para pensar em união. 2s (e que Deus proíba 3s ou mais) serviria apenas como marcadores que não estamos na solução onírica de exatamente n matrizes adicionando à matriz all 1s, o número de 2s e superior medindo quantas matrizes extras usamos. (Cada matriz extra adiciona n à soma total no final.)
Brayden Ware

Respostas:

10

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.

(0 01 11 10 0)(1 10 00 01 1)in (onde o índice i +2 é interpretado como módulo n ). Para 0 ≤ jm , defina S j = { P E Q j : EC ∪ {{ m +1}}} e S = S 0 ∪… ∪ S m .

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 DC é uma cobertura de [ m ], podemos construir uma cobertura TS de tamanho (| D | +1) ( m +1) por T = { P E Q j : ES ∪ {{ m +1}}, 0≤ jm }.

Por outro lado, deixe TS 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, TS 0 cobre esses blocos. Além disso, TS 0 contém P { m +1}, pois, caso contrário, a entrada (2 m +1, 2 m +2) não seria coberta. Observe que ( TS 0 ) ∖ { P { m +1}} Corresponde a uma cobertura em conjunto C . Portanto, | TS 0 | ≥ k +1. Da mesma forma, para qualquer 0≤ jm , | TS 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

Tsuyoshi Ito
fonte
3
Tsuyoshi, suas respostas ultimamente têm sido bastante impressionantes. Algum dia, uma de suas provas neste site será citada como o Ito Lemma. :-)
Aaron Sterling
@ Aaron: Obrigado pelo seu comentário gentil. Observe que a coisa mais difícil da pergunta, a restrição ao caso de um subgrupo, é totalmente ignorada nesta resposta. É hora de pensar!
Tsuyoshi Ito
3
@ Aaron: Eu não sei se você disse isso intencionalmente, mas o lema de Ito foi adotado ( en.wikipedia.org/wiki/Ito_lemma ).
22410 Robin Ontário
11

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.

Stefan Langerman
fonte