{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T14:01:26Z","timestamp":1768831286981,"version":"3.49.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.14778\/3450980.3450983","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T16:17:16Z","timestamp":1618244236000},"page":"1150-1158","source":"Crossref","is-referenced-by-count":10,"title":["Optimizing bipartite matching in real-world applications by incremental cost computation"],"prefix":"10.14778","volume":"14","author":[{"given":"Tenindra","family":"Abeywickrama","sequence":"first","affiliation":[{"name":"Grab-NUS AI Lab"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor","family":"Liang","sequence":"additional","affiliation":[{"name":"Grab-NUS AI Lab"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kian-Lee","family":"Tan","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2894140"},{"key":"e_1_2_1_2_1","volume-title":"Muhammad Aamir Cheema, and Sabine Storandt","author":"Abeywickrama Tenindra","year":"2020","unstructured":"Tenindra Abeywickrama , Muhammad Aamir Cheema, and Sabine Storandt . 2020 . Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks. In ICAPS. 2--10. Tenindra Abeywickrama, Muhammad Aamir Cheema, and Sabine Storandt. 2020. Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks. In ICAPS. 2--10."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591844"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580113"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218069"},{"key":"e_1_2_1_8_1","volume-title":"Optimal Multi-taxi Dispatch for Mobile Taxi-Hailing Systems. In 2016 45th International Conference on Parallel Processing (ICPP). 294--303","author":"Gao G.","unstructured":"G. Gao , M. Xiao , and Z. Zhao . 2016 . Optimal Multi-taxi Dispatch for Mobile Taxi-Hailing Systems. In 2016 45th International Conference on Parallel Processing (ICPP). 294--303 . G. Gao, M. Xiao, and Z. Zhao. 2016. Optimal Multi-taxi Dispatch for Mobile Taxi-Hailing Systems. In 2016 45th International Conference on Parallel Processing (ICPP). 294--303."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788912"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070455"},{"key":"e_1_2_1_11_1","unstructured":"Y. Gong Y. Liu Y. Lin W. Chen and J. Zhang. 2019. Real-Time Taxi-Passenger Matching Using a Differential Evolutionary Fuzzy Controller. IEEE Transactions on Systems Man and Cybernetics: Systems (2019) 1--14.  Y. Gong Y. Liu Y. Lin W. Chen and J. Zhang. 2019. Real-Time Taxi-Passenger Matching Using a Differential Evolutionary Fuzzy Controller. IEEE Transactions on Systems Man and Cybernetics: Systems (2019) 1--14."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3003942"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(86)90073-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735888"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"e_1_2_1_17_1","volume-title":"Orlin and Yusin Lee","author":"James","year":"1993","unstructured":"James B. Orlin and Yusin Lee . 1993 . QuickMatch-a very fast algorithm for the assignment problem. (1993). James B. Orlin and Yusin Lee. 1993. QuickMatch-a very fast algorithm for the assignment problem. (1993)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.9"},{"key":"e_1_2_1_19_1","volume-title":"TESLA: A Centralized Taxi Dispatching Approach to Optimizing Revenue Efficiency with Global Fairness. In UrbComp.","author":"Rong Huigui","year":"2020","unstructured":"Huigui Rong , Qun Zhang , Xun Zhou , Hongbo Jiang , Da Cao , and Keqin Li . 2020 . TESLA: A Centralized Taxi Dispatching Approach to Optimizing Revenue Efficiency with Global Fairness. In UrbComp. Huigui Rong, Qun Zhang, Xun Zhou, Hongbo Jiang, Da Cao, and Keqin Li. 2020. TESLA: A Centralized Taxi Dispatching Approach to Optimizing Revenue Efficiency with Global Fairness. In UrbComp."},{"key":"e_1_2_1_20_1","unstructured":"Tim Roughgarden. 2016. CS261: A Second Course in Algorithms Lecture #5: Minimum-Cost Bipartite Matching. http:\/\/web.archive.org\/web\/20200212164159\/http:\/\/timroughgarden.org\/w16\/l\/l5.pdf  Tim Roughgarden. 2016. CS261: A Second Course in Algorithms Lecture #5: Minimum-Cost Bipartite Matching. http:\/\/web.archive.org\/web\/20200212164159\/http:\/\/timroughgarden.org\/w16\/l\/l5.pdf"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_41"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732240.2732249"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010206"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2006.05.004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140438"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219824"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098138"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204030"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2399306"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3450980.3450983","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:15:24Z","timestamp":1672222524000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3450980.3450983"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3]]},"references-count":29,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["10.14778\/3450980.3450983"],"URL":"https:\/\/doi.org\/10.14778\/3450980.3450983","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,3]]}}}