{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T07:37:06Z","timestamp":1770536226942,"version":"3.49.0"},"publisher-location":"New York, New York, USA","reference-count":34,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CAREER Award"],"award-info":[{"award-number":["CAREER Award"]}]},{"name":"National Science Foundation","award":["CCF-1535972"],"award-info":[{"award-number":["CCF-1535972"]}]},{"name":"National Science Foundation","award":["CCF-1527084"],"award-info":[{"award-number":["CCF-1527084"]}]},{"name":"Natural Sciences and Engineering Research Council","award":["327620-09"],"award-info":[{"award-number":["327620-09"]}]},{"name":"Natural Sciences and Engineering Research Council","award":["Discovery Accelerator Supplement award"],"award-info":[{"award-number":["Discovery Accelerator Supplement award"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1145\/3178876.3186104","type":"proceedings-article","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T15:53:48Z","timestamp":1523634828000},"page":"379-388","source":"Crossref","is-referenced-by-count":12,"title":["Minimizing Latency in Online Ride and Delivery Services"],"prefix":"10.1145","author":[{"given":"Abhimanyu","family":"Das","sequence":"first","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}]},{"given":"Sreenivas","family":"Gollapudi","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}]},{"given":"Anthony","family":"Kim","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}]},{"given":"Chaitanya","family":"Swamy","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}]}],"member":"320","reference":[{"key":"key-10.1145\/3178876.3186104-1","doi-asserted-by":"crossref","unstructured":"Hernán Abeledo, Ricardo Fukasawa, Artur Pessoa, and Eduardo Uchoa. 2013. The time dependent traveling salesman problem: polyhedra and algorithm. Mathematical Programming Computation 5, 1 (01 Mar 2013), 27--55. https: \/\/doi.org\/10.1007\/s12532-012-0047-y","DOI":"10.1007\/s12532-012-0047-y"},{"key":"key-10.1145\/3178876.3186104-2","unstructured":"Aamena Alshamsi, Sherief Abdallah, and Iyad Rahwan. 2009. Multiagent Selforganization for a Taxi Dispatch System. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '09)."},{"key":"key-10.1145\/3178876.3186104-3","unstructured":"F. Angel-Bello, Y. Cardona-Valdé A. Á. 2017. Mixed integer formulations for the multiple minimum latency problem. Operational Research (08 Feb 2017). https:\/\/doi.org\/10.1007\/s12351-017-0299--4"},{"key":"key-10.1145\/3178876.3186104-4","doi-asserted-by":"crossref","unstructured":"Aaron Archer and Anna Blasiak. 2010. Improved Approximation Algorithms for the Minimum Latency Problem via Prize-collecting Strolls. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 429--447. http:\/\/dl.acm.org\/citation.cfm?id=1873601.1873637","DOI":"10.1137\/1.9781611973075.36"},{"key":"key-10.1145\/3178876.3186104-5","doi-asserted-by":"crossref","unstructured":"Aaron Archer, Asaf Levin, and David P. Williamson. 2008. A Faster, Better Approximation Algorithm for the Minimum Latency Problem. SIAM J. Comput. 37, 5 (2008), 1472--1498. https:\/\/doi.org\/10.1137\/07068151X arXiv:https:\/\/doi.org\/10.1137\/07068151X","DOI":"10.1137\/07068151X"},{"key":"key-10.1145\/3178876.3186104-6","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora and George Karakostas. 2003. Approximation Schemes for Minimum Latency Problems. SIAM J. Comput. 32, 5 (2003), 1317--1337. https:\/\/doi.org\/ 10.1137\/S0097539701399654 arXiv:https:\/\/doi.org\/10.1137\/S0097539701399654","DOI":"10.1137\/S0097539701399654"},{"key":"key-10.1145\/3178876.3186104-7","unstructured":"Giorgio Ausiello, Stefano Leonardi, and Alberto Marchetti-Spaccamela. 2000. On Salesmen, Repairmen, Spiders, and Other Traveling Agents. Springer Berlin Heidelberg, Berlin, Heidelberg, 1--16."},{"key":"key-10.1145\/3178876.3186104-8","doi-asserted-by":"crossref","unstructured":"Avrim Blum, Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar Raghavan, and Madhu Sudan. 1994. The Minimum Latency Problem. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing (STOC '94). ACM, New York, NY, USA, 163--171. https:\/\/doi.org\/10.1145\/195058.195125","DOI":"10.1145\/195058.195125"},{"key":"key-10.1145\/3178876.3186104-9","doi-asserted-by":"crossref","unstructured":"Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, and Kunal Talwar. 2003. Paths, Trees, and Minimum Latency Tours. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS '03). IEEE Computer Society, Washington, DC, USA, 36--. http:\/\/dl.acm.org\/citation.cfm?id=946243. 946316 Chandra Chekuri, Nitish Korula, and Martin Pá2. Improved Algorithms for Orienteering and Related Problems. ACM Trans. Algorithms 8, 3, Article 23 (July 2012), 27 pages. https:\/\/doi.org\/10.1145\/2229163.2229167","DOI":"10.1145\/2229163.2229167"},{"key":"key-10.1145\/3178876.3186104-10","doi-asserted-by":"crossref","unstructured":"Chandra Chekuri and Amit Kumar. 2004. Maximum Coverage Problem with Group Budget Constraints and Applications. Springer Berlin Heidelberg, Berlin, Heidelberg, 72--83.","DOI":"10.1007\/978-3-540-27821-4_7"},{"key":"key-10.1145\/3178876.3186104-11","unstructured":"Abhimanyu Das, Sreenivas Gollapudi, Anthony Kim, Debmalya Panigrahi, and Chaitanya Swamy. 2018. Minimizing Latency in Online Ride and Delivery Services. (Feb 2018). Available at https:\/\/arxiv.org\/abs\/1802.02744."},{"key":"key-10.1145\/3178876.3186104-12","doi-asserted-by":"crossref","unstructured":"Willem E. de Paepe, Jan Karel Lenstra, Jiri Sgall, Ren A. Sitters, and Leen Stougie. 2004. Computer-Aided Complexity Classification of Dial-a-Ride Problems. INFORMS Journal on Computing 16, 2 (2004), 120--132. https:\/\/doi.org\/10. 1287\/ijoc.1030.0052 arXiv:https:\/\/doi.org\/10.1287\/ijoc.1030.0052","DOI":"10.1287\/ijoc.1030.0052"},{"key":"key-10.1145\/3178876.3186104-13","unstructured":"Jittat Fakcharoenphol, Chris Harrelson, and Satish Rao. 2003. The K-traveling Repairman Problem. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '03). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 655--664. http:\/\/dl.acm.org\/citation.cfm? id=644108.644215"},{"key":"key-10.1145\/3178876.3186104-14","unstructured":"Michel Goemans and Jon Kleinberg. 1996. An Improved Approximation Ratio for the Minimum Latency Problem. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '96). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 152--158. http:\/\/dl.acm.org\/citation.cfm? id=313852.313909"},{"key":"key-10.1145\/3178876.3186104-15","doi-asserted-by":"crossref","unstructured":"R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G.Rinnooy Kan. 1979. Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. In Discrete Optimization II, P.L. Hammer, E.L. Johnson, and B.H. Korte (Eds.). Annals of Discrete Mathematics, Vol. 5. Elsevier, 287 -- 326. https: \/\/doi.org\/10.1016\/S0167--5060(08)70356-X","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"key-10.1145\/3178876.3186104-16","doi-asserted-by":"crossref","unstructured":"Elias Koutsoupias, Christos Papadimitriou, and Mihalis Yannakakis. 1996. Searching a fixed graph. Springer Berlin Heidelberg, Berlin, Heidelberg, 280--289.","DOI":"10.1007\/3-540-61440-0_135"},{"key":"key-10.1145\/3178876.3186104-17","unstructured":"Zhixing Luo, Hu Qin, and Andrew Lim. 2014. Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints. European Journal of Operational Research 234, 1 (2014), 49--60. https:\/\/EconPapers.repec.org\/RePEc: eee:ejores:v:234:y:2014:i:1:p:49--60"},{"key":"key-10.1145\/3178876.3186104-18","doi-asserted-by":"crossref","unstructured":"Isabel Méndez-Diaz, Paula Zabala, and Abilio Lucena. 2008. A New Formulation for the Traveling Deliveryman Problem. Discrete Appl. Math. 156, 17 (Oct. 2008), 3223--3237. https:\/\/doi.org\/10.1016\/j.dam.2008.05.009","DOI":"10.1016\/j.dam.2008.05.009"},{"key":"key-10.1145\/3178876.3186104-19","unstructured":"Nenad Mladenović, Dragan Urosević, and Said Hanafi. 2013. Variable neighborhood search for the travelling deliveryman problem. 4 11, 1 (01 Mar 2013), 57--73. https:\/\/doi.org\/10.1007\/s10288-012-0212--1"},{"key":"key-10.1145\/3178876.3186104-20","doi-asserted-by":"crossref","unstructured":"Samuel Nucamendi-Guillèn, Iris Martinez-Salazar, Francisco Angel-Bello, and J Marcos Moreno-Vega. 2016. A mixed integer formulation and an efficient metaheuristic procedure for the k-Travelling Repairmen Problem. Journal of the Operational Research Society 67, 8 (01 Aug 2016), 1121--1134. https:\/\/doi.org\/10. 1057\/jors.2015.113","DOI":"10.1057\/jors.2015.113"},{"key":"key-10.1145\/3178876.3186104-21","doi-asserted-by":"crossref","unstructured":"Christos H. Papadimitriou and Mihalis Yannakakis. 1993. The Traveling Salesman Problem with Distances One and Two. Math. Oper. Res. 18, 1 (Feb. 1993), 1--11. https:\/\/doi.org\/10.1287\/moor.18.1.1","DOI":"10.1287\/moor.18.1.1"},{"key":"key-10.1145\/3178876.3186104-22","doi-asserted-by":"crossref","unstructured":"Ian Post and Chaitanya Swamy. 2015. Linear Programming-based Approximation Algorithms for Multi-vehicle Minimum Latency Problems. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '15). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 512--531. http:\/\/dl.acm.org\/citation.cfm?id=2722129.2722164","DOI":"10.1137\/1.9781611973730.35"},{"key":"key-10.1145\/3178876.3186104-23","doi-asserted-by":"crossref","unstructured":"Shiyou Qian, Jian Cao, Frèdèric Le Mouël, Issam Sahel, and Minglu Li. 2015. SCRAM: A Sharing Considered Route Assignment Mechanism for Fair Taxi Route Recommendations. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '15). ACM, New York, NY, USA, 955--964. https:\/\/doi.org\/10.1145\/2783258.2783261","DOI":"10.1145\/2783258.2783261"},{"key":"key-10.1145\/3178876.3186104-24","doi-asserted-by":"crossref","unstructured":"Meng Qu, Hengshu Zhu, Junming Liu, Guannan Liu, and Hui Xiong. 2014. A Costeffective Recommender System for Taxi Drivers. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '14). ACM, New York, NY, USA, 45--54. https:\/\/doi.org\/10.1145\/2623330.2623668","DOI":"10.1145\/2623330.2623668"},{"key":"key-10.1145\/3178876.3186104-25","doi-asserted-by":"crossref","unstructured":"Sartaj Sahni and Teofilo Gonzalez. 1976. P-Complete Approximation Problems. J. ACM 23, 3 (July 1976), 555--565. https:\/\/doi.org\/10.1145\/321958.321975","DOI":"10.1145\/321958.321975"},{"key":"key-10.1145\/3178876.3186104-26","unstructured":"Douglas O. Santos and Eduardo C. Xavier. 2013. Dynamic Taxi and Ridesharing: A Framework and Heuristics for the Optimization Problem. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI '13). AAAI Press, 2885--2891. http:\/\/dl.acm.org\/citation.cfm?id=2540128.2540544"},{"key":"key-10.1145\/3178876.3186104-27","doi-asserted-by":"crossref","unstructured":"Marcos Melo Silva, Anand Subramanian, Thibaut Vidal, and Luiz Satoru Ochi. 2012. A simple and effective metaheuristic for the Minimum Latency Problem. European Journal of Operational Research 221, 3 (2012), 513 -- 520. https:\/\/doi. org\/10.1016\/j.ejor.2012.03.044","DOI":"10.1016\/j.ejor.2012.03.044"},{"key":"key-10.1145\/3178876.3186104-28","doi-asserted-by":"crossref","unstructured":"Renè Sitters. 2002. The Minimum Latency Problem Is NP-Hard forWeighted Trees. In Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization. Springer-Verlag, London, UK, UK, 230--239. http:\/\/dl.acm.org\/citation.cfm?id=645591.660083","DOI":"10.1007\/3-540-47867-1_17"},{"key":"key-10.1145\/3178876.3186104-29","doi-asserted-by":"crossref","unstructured":"Renè Sitters. 2014. Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems. In Proceedings of the Twentyfifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '14). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 604--616. http: \/\/dl.acm.org\/citation.cfm?id=2634074.2634120","DOI":"10.1137\/1.9781611973402.46"},{"key":"key-10.1145\/3178876.3186104-30","doi-asserted-by":"crossref","unstructured":"M. Skutella. 2006. List Scheduling in Order of a-Points on a Single Machine. In Efficient Approximation and Online Algorithms. Springer, 250--291.","DOI":"10.1007\/11671541_9"},{"key":"key-10.1145\/3178876.3186104-31","doi-asserted-by":"crossref","unstructured":"John N. Tsitsiklis. 1992. Special cases of traveling salesman and repairman problems with time windows. Networks 22, 3 (1992), 263--282. https:\/\/doi.org\/10. 1002\/net.3230220305","DOI":"10.1002\/net.3230220305"},{"key":"key-10.1145\/3178876.3186104-32","unstructured":"Xianyuan Zhan, Xinwu Qian, and Satish V. Ukkusuri. 2014. Measuring the Efficiency of Urban Taxi Service System. In The Third International Workshop on Urban Computing (UrbComp '14)."},{"key":"key-10.1145\/3178876.3186104-33","doi-asserted-by":"crossref","unstructured":"Xudong Zheng, Xiao Liang, and Ke Xu. 2012. Where to Wait for a Taxi?. In Proceedings of the ACM SIGKDD International Workshop on Urban Computing (UrbComp '12). ACM, New York, NY, USA, 149--156. https:\/\/doi.org\/10.1145\/ 2346496.2346520","DOI":"10.1145\/2346496.2346520"},{"key":"key-10.1145\/3178876.3186104-34","doi-asserted-by":"crossref","unstructured":"Chenguang Zhu and Balaji Prabhakar. 2017. Reducing Inefficiencies in Taxi Systems. In Proceedings of the Fifty-Sixth IEEE Conference on Decision and Control (CDC '17).","DOI":"10.1109\/CDC.2017.8264609"}],"event":{"name":"the 2018 World Wide Web Conference","location":"Lyon, France","acronym":"WWW '18","number":"2018","sponsor":["SIGWEB, ACM Special Interest Group on Hypertext, Hypermedia, and Web","IW3C2, International World Wide Web Conference Committee"],"start":{"date-parts":[[2018,4,23]]},"end":{"date-parts":[[2018,4,27]]}},"container-title":["Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178876.3186104","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3186104&ftid=1957458&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:28Z","timestamp":1750212688000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=3178876.3186104"}},"subtitle":[],"proceedings-subject":"World Wide Web","short-title":[],"issued":{"date-parts":[[2018]]},"references-count":34,"URL":"https:\/\/doi.org\/10.1145\/3178876.3186104","relation":{},"subject":[],"published":{"date-parts":[[2018]]}}}