{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:53Z","timestamp":1740122453455,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,8,24]],"date-time":"2020-08-24T00:00:00Z","timestamp":1598227200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,24]],"date-time":"2020-08-24T00:00:00Z","timestamp":1598227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["71601152"],"award-info":[{"award-number":["71601152"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["10026743"],"award-info":[{"award-number":["10026743"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider an online car-sharing problem between two locations with advance bookings. Each customer submits a pair of requests, where each request specifies the pick-up time and the pick-up location: one request from <jats:italic>A<\/jats:italic> to <jats:italic>B<\/jats:italic>, and the other request from <jats:italic>B<\/jats:italic> to <jats:italic>A<\/jats:italic>, not necessary in this order. The scheduler aims to maximize the number of satisfied customers, where the schedule has to decide whether or not to accept a request pair immediately at the time when the request pair is submitted. This problem is called <jats:sc>OnlineTransfersForCommuting<\/jats:sc>. We present lower bounds on the competitive ratio for this problem with both fixed booking times and variable booking times, and propose two algorithms, greedy algorithm and balanced greedy algorithm, that achieve the best possible competitive ratios.<\/jats:p>","DOI":"10.1007\/s10878-020-00635-8","type":"journal-article","created":{"date-parts":[[2020,8,24]],"date-time":"2020-08-24T16:02:36Z","timestamp":1598284956000},"page":"1240-1263","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Online scheduling of car-sharing request pairs between two locations"],"prefix":"10.1007","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2006-0601","authenticated-orcid":false,"given":"Kelin","family":"Luo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yinfeng","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haodong","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,24]]},"reference":[{"key":"635_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703437843","volume":"36","author":"R Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda R, Halld\u00f3rsson MM, Naor J, Shachnai H, Shapira I (2006) Scheduling split intervals. SIAM J Comput 36:1\u201315","journal-title":"SIAM J Comput"},{"key":"635_CR2","doi-asserted-by":"crossref","unstructured":"Bei X, Zhang S (2018) Algorithms for trip-vehicle assignment in ride-sharing. In: Thirty-second AAAI conference on artificial intelligence, pp 3\u20139","DOI":"10.1609\/aaai.v32i1.11298"},{"key":"635_CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6hmov\u00e1 K, Disser Y, Mihal\u00e1k M, \u0160r\u00e1mek R (2016) Scheduling transfers of resources over time: towards car-sharing with flexible drop-offs. In: LATIN 2016: theoretical informatics. Springer, pp 220\u2013234","DOI":"10.1007\/978-3-662-49529-2_17"},{"key":"635_CR4","volume-title":"Online computation and competitive analysis","author":"A Borodin","year":"2005","unstructured":"Borodin A, El-Yaniv R (2005) Online computation and competitive analysis. Cambridge University Press, Cambridge"},{"key":"635_CR5","unstructured":"Dutta C, Sholley C (2018) Online matching in a ride-sharing platform. arXiv preprint arXiv:1806.10327"},{"key":"635_CR6","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs. Elsevier, Amsterdam"},{"key":"635_CR7","unstructured":"Gy\u00e1rf\u00e1s A, West D (1995) Multitrack interval graphs"},{"key":"635_CR8","unstructured":"Lipton R (1994) Online interval scheduling. In: Proceedings of the fifth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, pp 302\u2013311"},{"key":"635_CR9","doi-asserted-by":"crossref","unstructured":"Liu H, Luo K, Xu Y, Zhang H (2019) Car-sharing problem: online scheduling with flexible advance bookings. In: international conference on combinatorial optimization and applications. Springer, pp 340\u2013351","DOI":"10.1007\/978-3-030-36412-0_27"},{"key":"635_CR10","doi-asserted-by":"crossref","unstructured":"Luo K, Erlebach T, Xu Y (2018a) Car-sharing between two locations: online scheduling with flexible advance bookings. In: International computing and combinatorics conference. Springer, pp 242\u2013254","DOI":"10.1007\/978-3-319-94776-1_21"},{"key":"635_CR11","unstructured":"Luo K, Erlebach T, Xu Y (2018b) Car-sharing between two locations: online scheduling with two servers. In: 43rd international symposium on mathematical foundations of computer science (MFCS). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp 50:1\u201350:14"},{"key":"635_CR12","unstructured":"Luo K, Erlebach T, Xu Y (2018c) Online scheduling of car-sharing requests between two locations with many cars and flexible advance bookings. In: 29th international symposium on algorithms and computation (ISAAC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp 64:1\u201364:13"},{"key":"635_CR13","unstructured":"Luo K, Erlebach T, Xu Y (2019a) Car-sharing on a star network: on-line scheduling with k servers. In: 36th international symposium on theoretical aspects of computer science (STACS). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp 51:1\u201351:14"},{"key":"635_CR14","doi-asserted-by":"crossref","unstructured":"Luo K, Xu Y, Liu H (2019b) Online scheduling of car-sharing request pairs between two locations with advance bookings. In: 2019 international conference on industrial engineering and systems management (IESM). IEEE, pp 1\u20136","DOI":"10.1109\/IESM45758.2019.8948087"},{"key":"635_CR15","doi-asserted-by":"crossref","unstructured":"Nayyar K, Raghvendra S (2017) An input sensitive online algorithm for the metric bipartite matching problem. In: 2017 IEEE 58th annual symposium on foundations of computer science (FOCS). IEEE, pp 505\u2013515","DOI":"10.1109\/FOCS.2017.53"},{"key":"635_CR16","unstructured":"Raghvendra S (2018) Optimal analysis of an online algorithm for the bipartite matching problem on a line. arXiv preprint arXiv:1803.07206"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00635-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00635-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00635-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T18:00:15Z","timestamp":1657735215000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00635-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,24]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["635"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00635-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,8,24]]},"assertion":[{"value":"24 August 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}