{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T18:03:22Z","timestamp":1758477802768,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_5","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"52-65","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A Collection of Lower Bounds for Online Matching on the Line"],"prefix":"10.1007","author":[{"given":"Antonios","family":"Antoniadis","sequence":"first","affiliation":[]},{"given":"Carsten","family":"Fischer","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"T\u00f6nnis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Antoniadis, A., Barcelo, N., Nugent, M., Pruhs, K., Scquizzato, M.: A o(n)-competitive deterministic algorithm for online matching on a line. In: Proceedings of 12th International Workshop Approximations and Online Algorithms (WAOA), pp. 11\u201322 (2014)","DOI":"10.1007\/978-3-319-18263-6_2"},{"issue":"2","key":"5_CR2","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/s00453-012-9676-9","volume":"68","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Buchbinder, N., Gupta, A., Naor, J.: A randomized o(log2 k)-competitive algorithm for metric bipartite matching. Algorithmica 68(2), 390\u2013403 (2014)","journal-title":"Algorithmica"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-78773-0_20","volume-title":"LATIN 2008: Theoretical Informatics","author":"C Chung","year":"2008","unstructured":"Chung, C., Pruhs, K., Uthaisombut, P.: The online transportation problem: on the exponential boost of one extra server. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 228\u2013239. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78773-0_20"},{"issue":"1\u20133","key":"5_CR4","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.tcs.2004.10.028","volume":"332","author":"B Fuchs","year":"2005","unstructured":"Fuchs, B., Hochst\u00e4ttler, W., Kern, W.: Online matching on a line. Theo. Comput. Sci. 332(1\u20133), 251\u2013264 (2005)","journal-title":"Theo. Comput. Sci."},{"key":"5_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/978-3-642-31594-7_36","volume-title":"Automata, Languages, and Programming","author":"A Gupta","year":"2012","unstructured":"Gupta, A., Lewi, K.: The online metric matching problem for doubling metrics. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 424\u2013435. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_36"},{"issue":"3","key":"5_CR6","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1006\/jagm.1993.1026","volume":"14","author":"B Kalyanasundaram","year":"1993","unstructured":"Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"issue":"3","key":"5_CR7","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1137\/S0895480198342310","volume":"13","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: The online transportation problem. SIAM J. Discrete Math. 13(3), 370\u2013383 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"5_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","volume":"127","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Mitchell, S.G., Vazirani, V.V.: On-line algorithms for weighted bipartite matching and stable marriages. Theo. Comput. Sci. 127(2), 255\u2013267 (1994)","journal-title":"Theo. Comput. Sci."},{"issue":"2","key":"5_CR9","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.cosrev.2009.04.002","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E.: The k-server problem. Comput. Sci. Rev. 3(2), 105\u2013118 (2009)","journal-title":"Comput. Sci. Rev."},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-540-24592-6_14","volume-title":"Approximation and Online Algorithms","author":"E Koutsoupias","year":"2004","unstructured":"Koutsoupias, E., Nanavati, A.: The online matching problem on a line. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol. 2909, pp. 179\u2013191. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24592-6_14"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Nanavati, A., Poplawski, L.J.: Randomized online algorithms for minimum metric bipartite matching. In: Proceedings of 17th Symposium Discrete Algorithms (SODA), pp. 954\u2013959 (2006)","DOI":"10.1145\/1109557.1109662"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Nayyar, K., Raghvendra, S.: An input sensintive online algorithm for the metric bipartite matching problem. In: FOCS (2017, to appear). http:\/\/ieee-focs.org\/FOCS-2017-Papers\/3464a505.pdf","DOI":"10.1109\/FOCS.2017.53"},{"key":"5_CR13","unstructured":"Raghvendra, S.: A robust and optimal online algorithm for minimum metric bipartite matching. In: Approximation, Randomization, and Combinatorial Optimization, APPROX\/RANDOM, pp. 18:1\u201318:16 (2016)"},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/2902945.2902960","volume":"47","author":"R van Stee","year":"2016","unstructured":"van Stee, R.: SIGACT news online algorithms column 27: online matching on the line, part 1. SIGACT News 47(1), 99\u2013110 (2016)","journal-title":"SIGACT News"},{"issue":"2","key":"5_CR15","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/2951860.2951871","volume":"47","author":"R van Stee","year":"2016","unstructured":"van Stee, R.: SIGACT news online algorithms column 28: online matching on the line, part 2. SIGACT News 47(2), 40\u201351 (2016)","journal-title":"SIGACT News"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:00:50Z","timestamp":1709827250000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}