{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T14:36:54Z","timestamp":1725892614572},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642212031"},{"type":"electronic","value":"9783642212048"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21204-8_7","type":"book-chapter","created":{"date-parts":[[2011,5,28]],"date-time":"2011-05-28T05:15:25Z","timestamp":1306559725000},"page":"29-35","source":"Crossref","is-referenced-by-count":0,"title":["An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem"],"prefix":"10.1007","author":[{"given":"Wenqiang","family":"Dai","sequence":"first","affiliation":[]},{"given":"Yi","family":"Feng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: STOC 1998, pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., Khandekar, R., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. In: STOC 2001, pp. 21\u201329 (2001)","DOI":"10.1145\/380752.380755"},{"issue":"6","key":"7_CR3","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1287\/mnsc.35.6.645","volume":"35","author":"M.L. Brandeau","year":"1989","unstructured":"Brandeau, M.L., Chiu, S.S.: An overview of representative problems in location research. Management Science\u00a035(6), 645\u2013674 (1989)","journal-title":"Management Science"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-540-77918-6_17","volume-title":"Approximation and Online Algorithms","author":"M. Chrobak","year":"2008","unstructured":"Chrobak, M., Hurand, M.: Better bounds for incremental medians. In: Kaklamanis, C., Skutella, M. (eds.) WAOA 2007. LNCS, vol.\u00a04927, pp. 207\u2013217. Springer, Heidelberg (2008)"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/11682462_31","volume-title":"LATIN 2006: Theoretical Informatics","author":"M. Chrobak","year":"2006","unstructured":"Chrobak, M., Kenyon, C., Young, N.E.: Oblivious medians via online bidding. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 311\u2013322. Springer, Heidelberg (2006)"},{"volume-title":"Network and Discrete Location","year":"1995","key":"7_CR6","unstructured":"Daskin, M. (ed.): Network and Discrete Location. Wiley, New York (1995)"},{"volume-title":"Facility Location: A Survey of Applications and Methods","year":"1995","key":"7_CR7","unstructured":"Drezner, Z. (ed.): Facility Location: A Survey of Applications and Methods. Springer, New York (1995)"},{"volume-title":"Facility Location: Applications and Theory","year":"2002","key":"7_CR8","unstructured":"Drezner, Z., Hamacher, H. (eds.): Facility Location: Applications and Theory. Springer, Berlin (2002)"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1287\/trsc.5.2.212","volume":"5","author":"A.J. Goldman","year":"1971","unstructured":"Goldman, A.J.: Optimal center location in simple networks. Transportation Science\u00a05, 212\u2013221 (1971)","journal-title":"Transportation Science"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1287\/trsc.4.4.406","volume":"4","author":"A.J. Goldman","year":"1970","unstructured":"Goldman, A.J., Witzgall, C.J.: A localization theorem for optimal facility location. Transportation Science\u00a04, 406\u2013409 (1970)","journal-title":"Transportation Science"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. Journal of Algorithms\u00a031, 228\u2013248 (1999)","journal-title":"Journal of Algorithms"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0167-6377(91)90041-M","volume":"10","author":"R. Hassin","year":"1991","unstructured":"Hassin, R., Tamir, A.: Improved complexity bounds for location problems on the real line. Operations Research Letters\u00a010, 395\u2013402 (1991)","journal-title":"Operations Research Letters"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: STOC 2002, pp. 731\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Lin., G.L., Nagarajan, C., Rajamaran, R., Williamson, D.P.: A general approach for incremental approximation and hierarchical clustering. In: SODA 2002. ACM\/SIAM (2006)","DOI":"10.1145\/1109557.1109684"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Lin, J.H., Vitter, J.S.: \u03b5-approximations with minimum packing constraint violation. In: STOC 1992, pp. 771\u2013782 (1992)","DOI":"10.1145\/129712.129787"},{"volume-title":"Facilities Location: Models and Methods","year":"1988","key":"7_CR16","unstructured":"Love, R.F., Morris, J.G., Wesolowsky, G.O. (eds.): Facilities Location: Models and Methods. North Holland, New York (1988)"},{"issue":"3","key":"7_CR17","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"R.R. Mettu","year":"2003","unstructured":"Mettu, R.R., Plaxton, C.G.: The online median problem. SIAM Journal of Computing\u00a032(3), 816\u2013832 (2003)","journal-title":"SIAM Journal of Computing"},{"volume-title":"Discrete location theory","year":"1990","key":"7_CR18","unstructured":"Mirchandani, P., Francis, R. (eds.): Discrete location theory. Wiley Interscience, Hoboken (1990)"},{"issue":"3","key":"7_CR19","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1134\/S1990478908030125","volume":"2","author":"V.V. Shenmaier","year":"2008","unstructured":"Shenmaier, V.V.: An Approximate Solution Algorithm for the One-Dimensional Online Median Problem. Journal of Applied and Industrial Mathematics\u00a02(3), 421\u2013425 (2008)","journal-title":"Journal of Applied and Industrial Mathematics"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21204-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T08:10:46Z","timestamp":1560240646000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21204-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642212031","9783642212048"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21204-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}