Abstrakt. Maximum Carpool Matching problem är en stjärna förpackning problem i riktade grafer. Formellt, med tanke på en riktad graf G = (V, A), en kapacitetsfunktion c : V → N, och en vikt funktion w : A → R, en genomförbar carpool matchning är en trippel (P, D, M ), där P (passagerare) och D (drivare) bildar en partition av V, och M är en delmängd av A  till (P × D), under de begränsningar som för varje vertex I maximal Carpool Matching problem vi söker efter en matchning (P, D, M ) som maximerar den totala vikten av M. Problemet uppstår när man utformar en online carpool tjänst, såsom Zimride [1], som försöker ansluta mellan passagerare och förare baserat på (arbitrary) likhet funktion. Problemet är känt för att vara NP-hård, även för enhetliga vikter och utan kapacitetsbegränsningar. Vi presenterar en 3- approximation algoritm för problemet och 2- approximation algoritm för den oviktade varianten av problemet.
För maximal Carpool Matching problem, en 0,33-uppskattning algoritm och en 0,5-uppskattning algoritm för både det allmänna problemet och den oviktade varianten anges i REF.
Approximation Algorithms for the Maximum Carpool Matching Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}