{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T21:38:02Z","timestamp":1762033082535},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,1,8]],"date-time":"2013-01-08T00:00:00Z","timestamp":1357603200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,6]]},"DOI":"10.1007\/s00453-012-9737-0","type":"journal-article","created":{"date-parts":[[2013,1,7]],"date-time":"2013-01-07T15:58:03Z","timestamp":1357574283000},"page":"370-383","source":"Crossref","is-referenced-by-count":10,"title":["New Algorithms for Facility Location Problems on the Real Line"],"prefix":"10.1007","volume":"69","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,8]]},"reference":[{"issue":"4","key":"9737_CR1","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1145\/299917.299918","volume":"30","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., Sharir, M.: Efficient algorithms for geometric optimization. ACM Comput. Surv. 30(4), 412\u2013458 (1998)","journal-title":"ACM Comput. Surv."},{"key":"9737_CR2","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M., Moran, S., Shor, P., Wilbur, R.: Geometric applications of a matrix-searching algorithm. Algorithmica 2, 195\u2013208 (1987)","journal-title":"Algorithmica"},{"key":"9737_CR3","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02574380","volume":"12","author":"A. Aggarwal","year":"1994","unstructured":"Aggarwal, A., Schieber, B., Tokuyama, T.: Finding a minimum weight k-link path in graphs with concave monge property and applications. Discrete Comput. Geom. 12, 263\u2013280 (1994)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9737_CR4","first-page":"87","volume":"26","author":"V. Auletta","year":"1998","unstructured":"Auletta, V., Parente, D., Persiano, G.: Placing resources on a growing line. J. Algorithms 26(1), 87\u2013100 (1998)","journal-title":"J. Algorithms"},{"issue":"2","key":"9737_CR5","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01585739","volume":"46","author":"R. Chandrasekaran","year":"1990","unstructured":"Chandrasekaran, R., Tamir, A.: Algebraic optimization: the Fermat-Weber location problem. Math. Program. 46(2), 219\u2013224 (1990)","journal-title":"Math. Program."},{"issue":"6","key":"9737_CR6","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/j.orl.2011.08.001","volume":"39","author":"D.Z. Chen","year":"2011","unstructured":"Chen, D.Z., Wang, H.: Improved algorithms for path partition and related problems. Oper. Res. Lett. 39(6), 437\u2013440 (2011)","journal-title":"Oper. Res. Lett."},{"key":"9737_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-642-22300-6_18","volume-title":"Proc. of the Algorithms and Data Structures Symposium (WADS)","author":"D.Z. Chen","year":"2011","unstructured":"Chen, D.Z., Wang, H.: New algorithms for 1-D facility location and path equipartition problems. In: Proc. of the Algorithms and Data Structures Symposium (WADS). Lecture Notes in Computer Science, vol. 6844, pp. 207\u2013218. Springer, Berlin (2011)"},{"key":"9737_CR8","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"9737_CR9","volume-title":"Facility Location: Applications and Theory","author":"Z. Drezner","year":"2004","unstructured":"Drezner, Z., Hamacher, H.W.: Facility Location: Applications and Theory. Springer, New York (2004)"},{"issue":"3","key":"9737_CR10","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1137\/0215052","volume":"15","author":"M.E. Dyer","year":"1986","unstructured":"Dyer, M.E.: On a multidimensional search technique and its application to the Euclidean one centre problem. SIAM J. Comput. 15(3), 725\u2013738 (1986)","journal-title":"SIAM J. Comput."},{"key":"9737_CR11","first-page":"168","volume-title":"Proc. of the 2nd Annual ACM-SIAM Symposium of Discrete Algorithms (SODA)","author":"G.N. Frederickson","year":"1991","unstructured":"Frederickson, G.N.: Optimal algorithms for tree partitioning. In: Proc. of the 2nd Annual ACM-SIAM Symposium of Discrete Algorithms (SODA), pp. 168\u2013177 (1991)"},{"key":"9737_CR12","first-page":"135","volume-title":"Proc. of the 16th Annual ACM Symposium on Theory of Computing (STOC)","author":"H. Gabow","year":"1984","unstructured":"Gabow, H., Bentley, J., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. of the 16th Annual ACM Symposium on Theory of Computing (STOC), pp. 135\u2013143 (1984)"},{"issue":"6","key":"9737_CR13","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0020-0190(90)90215-J","volume":"33","author":"Z. Galil","year":"1990","unstructured":"Galil, Z., Park, K.: A linear-time algorithm for concave one-dimensional dynamic programming. Inf. Process. Lett. 33(6), 309\u2013311 (1990)","journal-title":"Inf. Process. Lett."},{"key":"9737_CR14","doi-asserted-by":"crossref","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. Oper. Res. Lett. 10, 395\u2013402 (1991)","journal-title":"Oper. Res. Lett."},{"key":"9737_CR15","unstructured":"Klawe, M.M.: A simple linear time algorithm for concave one-dimensional dynamic programming. Technical Report 89-16, University of British, Columbia, Vancouver, Canada (1989)"},{"issue":"3","key":"9737_CR16","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0196-6774(91)90016-R","volume":"12","author":"L. Larmore","year":"1991","unstructured":"Larmore, L., Schieber, B.: On-line dynamic programming with applications to the prediction of RNA secondary structure. J. Algorithms 12(3), 490\u2013515 (1991)","journal-title":"J. Algorithms"},{"issue":"1\u20134","key":"9737_CR17","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF01840442","volume":"1","author":"D.T. Lee","year":"1986","unstructured":"Lee, D.T., Wu, Y.F.: Geometric complexity of some location problems. Algorithmica 1(1\u20134), 193\u2013211 (1986)","journal-title":"Algorithmica"},{"issue":"5","key":"9737_CR18","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1287\/mnsc.22.5.614","volume":"22","author":"R.F. Love","year":"1976","unstructured":"Love, R.F.: One-dimensional facility location-allocation using dynamic programming. Manag. Sci. 22(5), 614\u2013617 (1976)","journal-title":"Manag. Sci."},{"issue":"4","key":"9737_CR19","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N.: Linear-time algorithms for linear programming in R 3 and related problems. SIAM J. Comput. 12(4), 759\u2013776 (1983)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9737_CR20","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1137\/0604028","volume":"4","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N., Zemel, E., Hakimi, S.L.: The maximum coverage location problem. SIAM J. Algebr. Discrete Methods 4(2), 253\u2013261 (1983)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"2","key":"9737_CR21","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1006\/jagm.1998.0955","volume":"29","author":"B. Schieber","year":"1998","unstructured":"Schieber, B.: Computing a minimum weight k-link path in graphs with the concave monge property. J. Algorithms 29(2), 204\u2013222 (1998)","journal-title":"J. Algorithms"},{"issue":"1","key":"9737_CR22","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1111\/j.1467-9574.2007.00347.x","volume":"61","author":"S. Hoesel van","year":"2007","unstructured":"van Hoesel, S., Wagelmans, A.: On the p-coverage problem on the real line. Stat. Neerl. 61(1), 16\u201334 (2007)","journal-title":"Stat. Neerl."},{"issue":"3","key":"9737_CR23","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/0196-6774(88)90032-6","volume":"9","author":"R. Wilber","year":"1988","unstructured":"Wilber, R.: The concave least-weight subsequence problem revisited. J. Algorithms 9(3), 418\u2013425 (1988)","journal-title":"J. Algorithms"},{"issue":"3","key":"9737_CR24","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0167-6377(00)00041-9","volume":"27","author":"G.J. Woeginger","year":"2000","unstructured":"Woeginger, G.J.: Monge strikes again: optimal placement of web proxies in the Internet. Oper. Res. Lett. 27(3), 93\u201396 (2000)","journal-title":"Oper. Res. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9737-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9737-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9737-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:11Z","timestamp":1559137511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9737-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,8]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["9737"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9737-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,8]]}}}