Complexidade do problema de casamento?

Suponha que você tenha machos e n fêmeas. Cada pessoa tem m atributos. Cada pessoa indica um conjunto de atributos que um possível candidato deve ter. Uma correspondência é um conjunto de pares. Cada par liga um macho a uma fêmea. A satisfação de uma correspondência é o número de atributos satisfeitos para a pessoa com menos sorte. $n$$n$$m$

É encontrar uma correspondência com a máxima satisfação de resolução eficiente ou é -Hard?$NP$

Vamos começar com a versão de decisão do problema: dado um "nível de satisfação" k, existe uma correspondência em que todos são correspondidos a uma pessoa com pelo menos k atributos desejados. Isso é apenas resolver a correspondência bipartida em um gráfico em que conectamos um homem e uma mulher se cada um obtém satisfação k do outro. (O tempo de execução parece O (mn ^ 2).) Para obter o problema original, faça uma pesquisa binária sobre k (para um fator extra de log (m) no tempo de execução).

Eu posso ter entendido mal a pergunta, porque minha resposta está em conflito com a de Serge. Na minha opinião, você está perguntando sobre o problema de atribuição de gargalos lineares. Sabe-se que isso foi resolvido em O (n ^ 2,5).

A fonte mais completa de informações é [1], embora eu realmente não goste do estilo do livro. Há também um site: http://www.assignmentproblems.com/linearBNAP.htm

EDIT: Para esclarecer, queremos uma atribuição de modo que a borda com custo máximo seja minimizada. O custo será o número máximo de atributos não atribuídos para o homem ou a mulher correspondentes.

EDIT2: Só posso oferecer referências do livro que citei. Três deles são:

1. G. Carpaneto e P. Toth Algorithm para a solução do problema de atribuição de gargalos. Computing , 27: 179-187m 1981
2. U. Derigs. Estratégias alternativas para resolver problemas de atribuição de gargalos - análise e resultados computacionais. Computing , 33: 95-106, 1984
3. U. Derigs e U. Zimmermann. Um método de caminho de aumento para resolver problemas de atribuição linear de gargalos. Computing , 19: 285-295, 1978

Você deve tentar se apossar do livro, pois lista alguns dos algoritmos disponíveis.

[1] Problemas de atribuição por Rainer Burkard, Mauro Dell'Amico, Silvano Martello

Como Tsuyoshi aponta em um comentário abaixo, não há razão para que uma solução para o problema tenha que ser uma correspondência estável. Portanto, a abordagem desta resposta provavelmente não funciona; especialmente porque acredito que a resposta de Tomer está correta.

Parece que a sua versão do problema do casamento é equivalente ao problema do casamento estável com arrependimento mínimo com laços, onde todos classificam os membros do outro sexo com possíveis laços, e o objetivo é maximizar a "felicidade" mínima.

$N^{1-\epsilon}$$\epsilon > 0$$N$

[1]: David Manlove, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita: variantes duras do casamento estável. Theor. Comput. Sci. 276 (1-2): 261-279 (2002). Postprint .

Não é apenas uma variação da correspondência bipartida máxima de custo mínimo? O peso para cada aresta é igual ao número de atributos satisfeitos e, em vez de encontrar a correspondência máxima que fornece a menor soma de peso, você deseja aquele para o qual o peso mínimo da aresta é maximizado.

Se esse entendimento estiver correto, eu pensaria que um algoritmo de caminho aumentado semelhante ao Busacker – Gowen [ 1 ] funcionaria. Em vez de sempre encontrar o caminho de aumento mais barato (em termos de soma de peso), você encontraria o melhor (maximizando a margem mínima). Isso, novamente, deve ser possível com uma leve modificação em qualquer algoritmo padrão de caminho mais curto (como o de Dijkstra, que é usado na versão do Busacker-Gowen usando o ajuste de peso de Edmonds e Karp).

$O(v|E|\lg |V|)$$O(vn^2\lg n)$