Maximale-cardinaliteitsmatchingEdit
Een fundamenteel probleem in combinatorische optimalisatie is het vinden van een maximale matching. Dit probleem kent verschillende algoritmen voor verschillende klassen van grafieken.
In een ongewogen bipartiete grafiek is het optimalisatieprobleem het vinden van een maximale kardinaliteitsovereenstemming. Het probleem wordt opgelost door het Hopcroft-Karp algoritme in O(√VE) tijd, en er zijn efficiëntere gerandomiseerde algoritmen, benaderingsalgoritmen, en algoritmen voor speciale klassen van grafieken zoals bipartiete planaire grafieken, zoals beschreven in het hoofdartikel.
maximale-gewichtsovereenstemmingEdit
In een gewogen bipartiete grafiek is het optimalisatieprobleem het vinden van een maximum-weight matching; een duaal probleem is het vinden van een minimum-weight matching. Dit probleem wordt vaak de maximaal gewogen bipartiete overeenkomst, of het toewijzingsprobleem genoemd. Het Hongaarse algoritme lost het toewijzingsprobleem op en was een van de eerste combinatorische optimalisatiealgoritmen. Het maakt gebruik van een aangepaste kortste pad-zoekmethode in het augmenting path-algoritme. Als voor deze stap het Bellman-Ford algoritme wordt gebruikt, wordt de looptijd van het Hongaarse algoritme O ( V 2 E ) {Displaystyle O(V^{2}E)}
, of de kosten van de randen kunnen worden verschoven met een potentiaal om O ( V 2 log V + V E ) {displaystyle O(V^{2}log {V}+VE)}
looptijd met het Dijkstra-algoritme en de Fibonacci-hoop.
In een niet-bipartiete gewogen grafiek kan het probleem van maximale gewichtsovereenstemming worden opgelost in tijd O ( V 2 E ) {Displaystyle O(V^{2}E)}
met behulp van Edmonds’ bloesemalgoritme.
Maximale overeenkomstenEdit
Een maximale overeenkomst kan worden gevonden met een eenvoudig greedy-algoritme. Een maximale overeenkomst is ook een maximale overeenkomst, en dus is het mogelijk om een grootste maximale overeenkomst te vinden in polynomiale tijd. Er is echter geen algoritme in polynomiale tijd bekend voor het vinden van een minimale maximale overeenkomst, dat wil zeggen een maximale overeenkomst die het kleinst mogelijke aantal randen bevat.
Een maximale overeenkomst met k randen is een randdominante verzameling met k randen. Omgekeerd, als we een minimale randdominante verzameling met k ribben krijgen, kunnen we een maximale overeenkomst met k ribben in polynomiale tijd construeren. Het probleem van het vinden van een minimale maximale overeenkomst is dus in wezen gelijk aan het probleem van het vinden van een minimale randdominante verzameling. Van beide optimalisatieproblemen is bekend dat ze NP-hard zijn; de beslissingsversies van deze problemen zijn klassieke voorbeelden van NP-complete problemen. Beide problemen kunnen binnen factor 2 benaderd worden in polynomiale tijd: vind eenvoudig een willekeurige maximale overeenkomst M.
TelproblemenEdit
Het aantal overeenstemmingen in een grafiek staat bekend als de Hosoya-index van de grafiek. Het is #P-compleet om deze grootheid te berekenen, zelfs voor tweepartiete grafieken. Het is ook #P-compleet om perfecte overeenkomsten te tellen, zelfs in bipartiete grafieken, omdat het berekenen van de permanentie van een willekeurige 0-1 matrix (een ander #P-compleet probleem) hetzelfde is als het berekenen van het aantal perfecte overeenkomsten in de bipartiete grafiek met de gegeven matrix als zijn biadjacency matrix. Er bestaat echter een volledig polynomiale tijd gerandomiseerd benaderingsschema voor het tellen van het aantal bipartiete overeenkomsten. Een opmerkelijke stelling van Kasteleyn stelt dat het aantal perfecte overeenkomsten in een vlakke grafiek precies in polynomiale tijd kan worden berekend via het FKT-algoritme.
Het aantal perfecte overeenkomsten in een volledige grafiek Kn (met n even) wordt gegeven door de dubbele factorie (n – 1)!!!. Het aantal overeenkomsten in volledige grafieken, zonder dat de overeenkomsten perfect moeten zijn, wordt gegeven door de telefoonnummers.
Het vinden van alle maximaal-matchbare randenEdit
Een van de basisproblemen in de matchingtheorie is om in een gegeven grafiek alle randen te vinden die tot een maximale matching in de grafiek kunnen worden uitgebreid (zulke randen worden maximaal-matchbare randen genoemd, of toegestane randen). Algoritmen voor dit probleem zijn onder andere:
- Voor algemene grafieken is een deterministisch algoritme in tijd O ( V E ) {\displaystyle O(VE)}
en een gerandomiseerd algoritme in tijd O ~ ( V 2,376 ) {\displaystyle {tilde {O}(V^{2,376})}
.
- Voor tweepartiete grafieken, als een enkele maximale overeenkomst wordt gevonden, loopt een deterministisch algoritme in tijd O ( V + E ) {\displaystyle O(V+E)}
.
Online bipartiete matchingEdit
Het probleem van het ontwikkelen van een online algoritme voor matching werd voor het eerst beschouwd door Richard M. Karp, Umesh Vazirani, en Vijay Vazirani in 1990.
In de online setting komen knooppunten aan de ene kant van de bipartiete grafiek één voor één binnen en moeten ofwel onmiddellijk gematcht worden aan de andere kant van de grafiek ofwel weggegooid worden. Dit is een natuurlijke veralgemening van het secretarisprobleem en heeft toepassingen op online advertentieveilingen. Het beste online algoritme, voor het ongewogen maximalisatiegeval met een willekeurig aankomstmodel, bereikt een concurrerende ratio van 0,696.