{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T17:12:44Z","timestamp":1744218764993,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T00:00:00Z","timestamp":1581552000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T00:00:00Z","timestamp":1581552000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JST PRESTO Grant Number JPMJPR1753"],"award-info":[{"award-number":["JST PRESTO Grant Number JPMJPR1753"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s00453-020-00688-5","type":"journal-article","created":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T07:12:22Z","timestamp":1581577942000},"page":"2087-2106","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Distance-Constrained Matroid Median Problem"],"prefix":"10.1007","volume":"82","author":[{"given":"Naoyuki","family":"Kamiyama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,13]]},"reference":[{"key":"688_CR1","doi-asserted-by":"crossref","unstructured":"Alamdari, S., Shmoys, D.: A bicriteria approximation algorithm for the $$k$$-center and $$k$$-median problems. In: Proceedings of the 15th Workshop on Approximation and Online Algorithms, Lecture Notes in Computer Science, vol. 10787, pp. 66\u201375 (2017)","DOI":"10.1007\/978-3-319-89441-6_6"},{"issue":"3","key":"688_CR2","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"key":"688_CR3","doi-asserted-by":"crossref","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for $$k$$-median, and positive correlation in budgeted optimization. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 737\u2013756 (2015)","DOI":"10.1137\/1.9781611973730.50"},{"issue":"4","key":"688_CR4","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34(4), 803\u2013824 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"688_CR5","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"M Charikar","year":"2002","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci. 65(1), 129\u2013149 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"688_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., Li, S.: A dependent LP-rounding approach for the $$k$$-median problem. In: Proceedings of the 39th International Colloquium on Automata, Languages and Programming, Part I, Lecture Notes in Computer Science, vol. 7391, pp. 194\u2013205 (2012)","DOI":"10.1007\/978-3-642-31594-7_17"},{"issue":"1","key":"688_CR7","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s00453-015-0010-1","volume":"75","author":"DZ Chen","year":"2016","unstructured":"Chen, D.Z., Li, J., Liang, H., Wang, H.: Matroid and knapsack center problems. Algorithmica 75(1), 27\u201352 (2016)","journal-title":"Algorithmica"},{"key":"688_CR8","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"688_CR9","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1007\/s00453-011-9547-9","volume":"63","author":"M Hajiaghayi","year":"2012","unstructured":"Hajiaghayi, M., Khandekar, R., Kortsarz, G.: Local search algorithms for the red\u2013blue median problem. Algorithmica 63(4), 795\u2013814 (2012)","journal-title":"Algorithmica"},{"issue":"2","key":"688_CR10","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the $$k$$-center problem. Math. Oper. Res. 10(2), 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"key":"688_CR11","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pp. 731\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"issue":"2","key":"688_CR12","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and $$k$$-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"688_CR13","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1287\/moor.2014.0678","volume":"40","author":"R Krishnaswamy","year":"2015","unstructured":"Krishnaswamy, R., Kumar, A., Nagarajan, V., Sabharwal, Y., Saha, B.: Facility location with matroid or knapsack constraints. Math. Oper. Res. 40(2), 446\u2013459 (2015)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"688_CR14","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1137\/130938645","volume":"45","author":"S Li","year":"2016","unstructured":"Li, S., Svensson, O.: Approximating $$k$$-median via pseudo-approximation. SIAM J. Comput. 45(2), 530\u2013547 (2016)","journal-title":"SIAM J. Comput."},{"key":"688_CR15","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001","volume-title":"Matroid Theory","author":"JG Oxley","year":"2011","unstructured":"Oxley, J.G.: Matroid Theory, 2nd edn. Oxford University Press, Oxford (2011)","edition":"2"},{"key":"688_CR16","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"issue":"4","key":"688_CR17","doi-asserted-by":"crossref","first-page":"49:1","DOI":"10.1145\/2963170","volume":"12","author":"C Swamy","year":"2016","unstructured":"Swamy, C.: Improved approximation algorithms for matroid and knapsack median problems and applications. ACM Trans. Algorithms 12(4), 49:1\u201349:22 (2016)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00688-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00688-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00688-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:38:12Z","timestamp":1613090292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00688-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,13]]},"references-count":17,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["688"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00688-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,2,13]]},"assertion":[{"value":"2 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}