{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:45Z","timestamp":1740109425147,"version":"3.37.3"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,6,22]],"date-time":"2017-06-22T00:00:00Z","timestamp":1498089600000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00224-017-9780-y","type":"journal-article","created":{"date-parts":[[2017,6,22]],"date-time":"2017-06-22T01:54:39Z","timestamp":1498096479000},"page":"1351-1365","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Speeding up dynamic programming in the line-constrained k-median"],"prefix":"10.1007","volume":"62","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9633-7139","authenticated-orcid":false,"given":"\u0141ukasz","family":"Zatorski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,22]]},"reference":[{"issue":"1-4","key":"9780_CR1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M. M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica 2(1-4), 195\u2013208 (1987)","journal-title":"Algorithmica"},{"issue":"1","key":"9780_CR2","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF02187906","volume":"3","author":"C Bajaj","year":"1988","unstructured":"Bajaj, C.: The algebraic degree of geometric optimization problems. Discrete Comput. Geom. 3(1), 177\u2013191 (1988)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9780_CR3","first-page":"17","volume":"6","author":"W Bein","year":"2009","unstructured":"Bein, W., Golin, M. J., Larmore, L. L., Zhang, Y.: The knuth\u2013Yao quadrangle-inequality speedup is a consequence of total monotonicity. ACM Trans. Algorithms (TALG) 6(1), 17 (2009)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"4","key":"9780_CR4","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R. W., Pratt, V. R., Rivest, R. L., Tarjan, R. E.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"9780_CR5","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."},{"issue":"1","key":"9780_CR6","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(92)90135-3","volume":"92","author":"Z Galil","year":"1992","unstructured":"Galil, Z., Park, K.: Dynamic programming with convexity, concavity and sparsity. Theor. Comput. Sci. 92(1), 49\u201376 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"9780_CR7","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841\u2013850. Society for Industrial and Applied Mathematics","author":"R Grossi","year":"2003","unstructured":"Grossi, R., Gupta, A., Vitter, J. S.: High-order entropy-compressed text indexes Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841\u2013850. Society for Industrial and Applied Mathematics (2003)"},{"issue":"1","key":"9780_CR8","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N., Supowit, K. J.: On the complexity of some common geometric location problems. SIAM J. Comput. 13(1), 182\u2013196 (1984)","journal-title":"SIAM J. Comput."},{"key":"9780_CR9","volume-title":"Algorithms and Computation, pp. 323\u2013332. Springer","author":"G Navarro","year":"2011","unstructured":"Navarro, G., Russo, L. M.: Space-efficient data-analysis queries on grids Algorithms and Computation, pp. 323\u2013332. Springer (2011)"},{"issue":"2","key":"9780_CR10","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. Journal of Algorithms 29(2), 204\u2013222 (1998)","journal-title":"Journal of Algorithms"},{"key":"9780_CR11","volume-title":"Algorithms and Computation, pp. 3\u201314. Springer","author":"H Wang","year":"2014","unstructured":"Wang, H., Zhang, J.: Line-constrained K-median, K-means, and K-center problems in the plane Algorithms and Computation, pp. 3\u201314. Springer (2014)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9780-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9780-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9780-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,6,1]],"date-time":"2018-06-01T21:53:21Z","timestamp":1527890001000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9780-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,22]]},"references-count":11,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["9780"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9780-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,6,22]]}}}