{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:10:32Z","timestamp":1784110232432,"version":"3.55.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T00:00:00Z","timestamp":1589932800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T00:00:00Z","timestamp":1589932800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["497\/14"],"award-info":[{"award-number":["497\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s00453-020-00719-1","type":"journal-article","created":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T00:02:32Z","timestamp":1589932952000},"page":"3165-3182","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Local Search Algorithms for the Maximum Carpool Matching Problem"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2430-102X","authenticated-orcid":false,"given":"Gilad","family":"Kutiel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,5,20]]},"reference":[{"issue":"2","key":"719_CR1","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.ejor.2012.05.028","volume":"223","author":"NAH Agatz","year":"2012","unstructured":"Agatz, N.A.H., Erera, A.L., Savelsbergh, M.W.P., Wang, X.: Optimization for dynamic ride-sharing: a review. Eur. J. Oper. Res. 223(2), 295\u2013303 (2012)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"719_CR2","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s00453-004-1087-0","volume":"39","author":"EM Arkin","year":"2004","unstructured":"Arkin, E.M., Hassin, R., Rubinstein, S., Sviridenko, M.: Approximations for maximum transportation with permutable supply vector and other capacitated star packing problems. Algorithmica 39(2), 175\u2013187 (2004)","journal-title":"Algorithmica"},{"key":"719_CR3","doi-asserted-by":"crossref","unstructured":"Athanassopoulos, S., Caragiannis, I., Kaklamanis, C., Kyropoulou, M.: An improved approximation bound for spanning star forest and color saving. In: 34th International Symposium on Mathematical Foundations of Computer Science, pp. 90\u2013101 (2009)","DOI":"10.1007\/978-3-642-03816-7_9"},{"key":"719_CR4","unstructured":"Blablacar. https:\/\/www.blablacar.com"},{"key":"719_CR5","doi-asserted-by":"crossref","unstructured":"Bar-Noy, A., Peleg, D., Rabanca, G., Vigan, I.: Improved approximation algorithms for weighted 2-path partitions. In: 23rd Annual European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 9294, pp. 953\u2013964 (2015)","DOI":"10.1007\/978-3-662-48350-3_79"},{"issue":"3","key":"719_CR6","first-page":"178","volume":"7","author":"P Berman","year":"2000","unstructured":"Berman, P.: A $d\/2$ approximation for maximum weight independent set in $d$-claw free graphs. Nord. J. Comput. 7(3), 178\u2013184 (2000)","journal-title":"Nord. J. Comput."},{"key":"719_CR7","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 392\u2013403 (2016)","DOI":"10.1137\/1.9781611974331.ch29"},{"issue":"5","key":"719_CR8","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/130929205","volume":"44","author":"N Buchbinder","year":"2015","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time (1\/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5), 1384\u20131402 (2015)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"719_CR9","doi-asserted-by":"publisher","first-page":"2189","DOI":"10.1137\/080735503","volume":"39","author":"D Chakrabarty","year":"2010","unstructured":"Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. SIAM J. Comput. 39(6), 2189\u20132211 (2010)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"719_CR10","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1006\/jagm.2000.1155","volume":"39","author":"B Chandra","year":"2001","unstructured":"Chandra, B., Halld\u00f3rsson, M.M.: Greedy local improvement and weighted set packing approximation. J. Algorithms 39(2), 223\u2013240 (2001)","journal-title":"J. Algorithms"},{"issue":"3","key":"719_CR11","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/s00453-011-9607-1","volume":"65","author":"N Chen","year":"2013","unstructured":"Chen, N., Engelberg, R., Nguyen, C.T., Raghavendra, P., Rudra, A., Singh, G.: Improved approximation algorithms for the spanning star forest problem. Algorithmica 65(3), 498\u2013516 (2013)","journal-title":"Algorithmica"},{"key":"719_CR12","unstructured":"Hartman, I.B.-A.: Optimal assignment for carpooling (submitted)"},{"key":"719_CR13","doi-asserted-by":"crossref","unstructured":"Hartman, I.B.-A., Keren, D., Dbai, A.A., Cohen, E., Knapen, L., Yasar, A.-U.-H., Janssens, D.: Theory and practice in large carpooling problems. In: 5th International Conference on Ambient Systems, Networks and Technologies, pp. 339\u2013347 (2014)","DOI":"10.1016\/j.procs.2014.05.433"},{"key":"719_CR14","doi-asserted-by":"crossref","unstructured":"Knapen, L., Keren, D., Yasar, A.-U.-H., Cho, S., Bellemans, T., Janssens, D., Wets, G.: Estimating scalability issues while finding an optimal assignment for carpooling. In: 4th International Conference on Ambient Systems, Networks and Technologies, pp. 372\u2013379 (2013)","DOI":"10.1016\/j.procs.2013.06.051"},{"issue":"3","key":"719_CR15","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s12652-013-0197-4","volume":"5","author":"L Knapen","year":"2014","unstructured":"Knapen, L., Yasar, A.-U.-H., Cho, S., Keren, D., Dbai, A.A., Bellemans, T., Janssens, D., Wets, G., Schuster, A., Sharfman, I., Bhaduri, K.: Exploiting graph-theoretic tools for matching in carpooling applications. J. Ambient Intell. Hum. Comput. 5(3), 393\u2013407 (2014)","journal-title":"J. Ambient Intell. Hum. Comput."},{"key":"719_CR16","doi-asserted-by":"crossref","unstructured":"Kutiel, G.: Approximation algorithms for the maximum carpool matching problem. In: 12th International Computer Science Symposium in Russia, Lecture Notes in Computer Science, vol. 10304, pp. 206\u2013216 (2017)","DOI":"10.1007\/978-3-319-58747-9_19"},{"key":"719_CR17","unstructured":"Moovit carpool. https:\/\/moovitapp.com\/"},{"issue":"3","key":"719_CR18","doi-asserted-by":"publisher","first-page":"946","DOI":"10.1137\/070682150","volume":"38","author":"CT Nguyen","year":"2008","unstructured":"Nguyen, C.T., Shen, J., Hou, M., Sheng, L., Miller, W., Zhang, L.: Approximating the spanning star forest problem and its application to genomic sequence alignment. SIAM J. Comput. 38(3), 946\u2013962 (2008)","journal-title":"SIAM J. Comput."},{"key":"719_CR19","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. In 12th Annual ACM Symposium on Theory of Computing, pp. 229\u2013234 (1988)","DOI":"10.1145\/62212.62233"},{"key":"719_CR20","unstructured":"Waze. https:\/\/www.waze.com\/"},{"key":"719_CR21","unstructured":"Zimride by enterprise. https:\/\/zimride.com\/"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00719-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00719-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00719-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T07:38:09Z","timestamp":1621496289000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00719-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,20]]},"references-count":21,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["719"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00719-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,20]]},"assertion":[{"value":"2 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}