I detta dokument betraktar vi problemet med att beräkna en "optimal" populär matchning. Vi antar att vår input instans G = (A  till P, E 1 till · · · · till E r ) medger en populär matchning och här är vi ombedda att returnera inte någon populär matchning utan en optimal populär matchning, där definitionen av optimalitet ges som en del av problemet uttalande; till exempel, optimalitet kan vara rättvisa i vilket fall vi är skyldiga att returnera en rättvis populär matchning. Vi visar en O(n 2 + m) algoritm för detta problem, förutsatt att preferenslistorna är strikt, där m är antalet kanter i G och n är antalet sökande.
Kavitha och Nasre REF beskrev algoritmer för att bestämma en optimal populär matchning för olika tolkningar av optimalitet.
Optimal popular matchings
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}