Proceedings of the VLDB Endowment · 2021 · 11 citations · 23 references
ComputingComputer ScienceAlgorithmsOptimizationTransportationAssignment ProblemsCombinatorial OptimizationShortest Path AlgorithmsTransportation ProblemsBipartite MatchingCombinatorial Optimization HeuristicsMatchingMatching AlgorithmsMatching ProblemsOptimal MatchingShortest PathsVehicle Assignment
The Kuhn-Munkres (KM) algorithm is a classical combinatorial optimization algorithm that is widely used for minimum cost bipartite matching in many real-world applications, such as transportation. For example, a ride-hailing service may use it to find the optimal assignment of drivers to passengers to minimize the overall wait time. Typically, given two bipartite sets, this process involves computing the edge costs between all bipartite pairs and finding an optimal matching. However, existing works overlook the impact of edge cost computation on the overall running time. In reality, edge computation often significantly outweighs the computation of the optimal assignment itself, as in the case of assigning drivers to passengers which involves computation of expensive graph shortest paths. Following on from this observation, we observe common real-world settings exhibit a useful property that allows us to incrementally compute edge costs only as required using an inexpensive lower-bound heuristic. This technique significantly reduces the overall cost of assignment compared to the original KM algorithm, as we demonstrate experimentally on multiple real-world data sets, workloads, and problems. Moreover, our algorithm is not limited to this domain and is potentially applicable in other settings where lower-bounding heuristics are available.
23
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations
Maximal Flow Through a Network
L. R. Ford, D. R. Fulkerson · Canadian Journal of Mathematics · 1956 · 2.3K citations · Full text
Matching, Euler tours and the Chinese postman
Jack Edmonds, Ellis L. Johnson · Mathematical Programming · 1973 · 987 citations