Cardinalidade máxima de correspondênciaEditar
Um problema fundamental na otimização combinatória é encontrar uma correspondência máxima. Este problema tem vários algoritmos para diferentes classes de gráficos.
Em um gráfico bipartido não ponderado, o problema da otimização é encontrar um emparelhamento máximo de cardinalidade. O problema é resolvido pelo algoritmo Hopcroft-Karp no tempo O(√VE), e há algoritmos randomizados mais eficientes, algoritmos de aproximação, e algoritmos para classes especiais de gráficos como gráficos planares bipartidos, como descrito no artigo principal.
Casamento de peso máximoEditar
Em um gráfico bipartido ponderado, o problema de otimização é encontrar uma combinação de peso máximo; um problema duplo é encontrar uma combinação de peso mínimo. Este problema é muitas vezes chamado de correspondência bipartida máxima ponderada, ou o problema de atribuição. O algoritmo húngaro resolve o problema da atribuição e foi um dos inícios dos algoritmos de otimização combinatória. Ele usa uma pesquisa modificada do caminho mais curto no algoritmo de aumento do caminho. Se o algoritmo Bellman-Ford for usado para este passo, o tempo de execução do algoritmo Húngaro torna-se O ( V 2 E ) {\i1}displaystyle O(V^{2}E)}
, ou o custo da borda pode ser deslocado com um potencial para alcançar O ( V 2 log V + V E ) {\i1}displaystyle O(V^{2}}log {V}+VE)}
tempo de execução com o algoritmo Dijkstra e a pilha de Fibonacci.
Em um gráfico não-bipartido, o problema de correspondência de peso máximo pode ser resolvido no tempo O ( V 2 E ) {\i1}displaystyle O(V^{2}E)}
usando o algoritmo de floração de Edmonds.
Combinações máximasEditar
Uma combinação máxima pode ser encontrada com um algoritmo simples e ganancioso. Uma correspondência máxima é também uma correspondência máxima, e por isso é possível encontrar uma correspondência máxima maior em tempo polinomial. Contudo, nenhum algoritmo de tempo polinomial é conhecido por encontrar uma correspondência máxima mínima, ou seja, uma correspondência máxima que contém o menor número possível de arestas.
Uma correspondência máxima com k arestas é um conjunto dominante de arestas com k arestas. Por outro lado, se nos for dado um conjunto dominando uma aresta mínima com k bordas, podemos construir uma correspondência máxima com k bordas em tempo polinomial. Portanto, o problema de encontrar uma concordância máxima mínima é essencialmente igual ao problema de encontrar um conjunto dominador de aresta mínima. Ambos estes dois problemas de otimização são conhecidos por serem NP-duros; as versões de decisão destes problemas são exemplos clássicos de problemas NP-completos. Ambos os problemas podem ser aproximados dentro do fator 2 em tempo polinomial: simplesmente encontre uma correspondência máxima arbitrária M.
Problemas de contagemEditar
O número de correspondências em um gráfico é conhecido como o índice Hosoya do gráfico. É #P-completo para calcular esta quantidade, mesmo para gráficos bipartidos. Também é #P-completo para contar correspondências perfeitas, mesmo em gráficos bipartidos, pois computar o permanente de uma matriz 0-1 arbitrária (outro problema #P-completo) é o mesmo que computar o número de correspondências perfeitas no gráfico bipartido tendo a matriz dada como sua matriz de biadjacência. No entanto, existe um esquema de aproximação totalmente polinomial de tempo aleatório para contar o número de correspondências bipartites. Um teorema notável de Kasteleyn afirma que o número de correspondências perfeitas em um gráfico planar pode ser computado exatamente no tempo polinomial através do algoritmo FKT.
O número de correspondências perfeitas em um gráfico completo Kn (com n pares) é dado pelo fatorial duplo (n – 1)! Os números de correspondências em gráficos completos, sem limitar as correspondências a serem perfeitas, são dados pelos números de telefone.
Encontrar todas as bordas que podem ser combinadas ao máximoEditar
Um dos problemas básicos na teoria da correspondência é encontrar em um determinado gráfico todas as bordas que podem ser estendidas até uma correspondência máxima no gráfico (tais bordas são chamadas de bordas com correspondência máxima, ou bordas permitidas). Algoritmos para este problema incluem:
- Para gráficos gerais, um algoritmo determinístico no tempo O ( V E ) {\\i1} {\i1}displaystyle O(VE)}
e um algoritmo randomizado no tempo O ~ ( V 2.376 ) {\i1}(V^{2.376})}(V^{2.376})}
.
- Para gráficos bipartidos, se for encontrada uma única correspondência máxima, um algoritmo determinístico corre no tempo O ( V + E ) {\\\i1}displaystyle O(V+E)}
.
>
Equilíbrio bipartido onlineEditar
O problema do desenvolvimento de um algoritmo online para o matching foi primeiramente considerado por Richard M. Karp, Umesh Vazirani e Vijay Vazirani em 1990.
Na configuração online, os nós de um lado do gráfico bipartido chegam um de cada vez e devem ser imediatamente combinados com o outro lado do gráfico ou descartados. Esta é uma generalização natural do problema da secretária e tem aplicações para leilões de anúncios online. O melhor algoritmo online, para o caso de maximização não ponderada com um modelo de chegada aleatória, atinge uma relação competitiva de 0,696,