{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:48:32Z","timestamp":1774421312439,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,8,12]],"date-time":"2015-08-12T00:00:00Z","timestamp":1439337600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,8,12]],"date-time":"2015-08-12T00:00:00Z","timestamp":1439337600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Basic Research Program of China","doi-asserted-by":"crossref","award":["2015CB358700, 2011CBA00300, 2011CBA00301"],"award-info":[{"award-number":["2015CB358700, 2011CBA00300, 2011CBA00301"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61202009, 61033001, 61361136003"],"award-info":[{"award-number":["61202009, 61033001, 61361136003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1317143"],"award-info":[{"award-number":["CCF-1317143"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217906"],"award-info":[{"award-number":["CCF-1217906"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,5]]},"DOI":"10.1007\/s00453-015-0010-1","type":"journal-article","created":{"date-parts":[[2015,8,11]],"date-time":"2015-08-11T14:42:05Z","timestamp":1439304125000},"page":"27-52","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Matroid and Knapsack Center Problems"],"prefix":"10.1007","volume":"75","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[]},{"given":"Jian","family":"Li","sequence":"additional","affiliation":[]},{"given":"Hongyu","family":"Liang","sequence":"additional","affiliation":[]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,12]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Panigrahy, R., Feder, T., Thomas, D., Kenthapadi, K., Khuller, S., Zhu, A.: Achieving Anonymity via Clustering, vol. 6, p. 49. ACM (2010)","DOI":"10.1145\/1798596.1798602"},{"key":"10_CR2","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the Twelfth Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 642\u2013651. Society for Industrial and Applied Mathematics (2001)"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Charikar, M., Li, S.: A dependent lp-rounding approach for the k-median problem. In: International Colloquium on Automata, Languages, and Programming, pp. 194\u2013205. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-31594-7_17"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Chechik, S., Peleg, D.: The fault tolerant capacitated k-center problem. In: Structural Information and Communication Complexity, pp. 13\u201324. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-31104-8_2"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Chen, D.Z., Wang, H.: Efficient algorithms for the weighted k-center problem on a real line. In: International Symposium on Algorithm and Computation, pp. 584\u2013593. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-25591-5_60"},{"key":"10_CR6","unstructured":"Chen, K.: A constant factor approximation algorithm for k-median clustering with outliers. In: Proceedings of the Nineteenth Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 826\u2013835. Society for Industrial and Applied Mathematics (2008)"},{"issue":"4","key":"10_CR7","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/1082036.1082038","volume":"52","author":"J Chuzhoy","year":"2005","unstructured":"Chuzhoy, J., Guha, S., Halperin, E., Khanna, S., Kortsarz, G., Krauthgamer, R., Naor, J.: Asymmetric $$k$$-center is $$\\log ^{*}n$$-hard to approximate. J. ACM 52(4), 538\u2013551 (2005)","journal-title":"J. ACM"},{"issue":"1","key":"10_CR8","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/7531.7537","volume":"34","author":"R Cole","year":"1987","unstructured":"Cole, R.: Slowing down sorting networks to obtain faster sorting algorithms. J. ACM 34(1), 200\u2013208 (1987)","journal-title":"J. ACM"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Cygan, M., Hajiaghayi, M., Khuller, S.: LP rounding for $$k$$-centers with non-uniform hard capacities. In: IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 273\u2013282 (2012)","DOI":"10.1109\/FOCS.2012.63"},{"issue":"3","key":"10_CR10","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0021-9800(70)80083-7","volume":"8","author":"J Edmonds","year":"1970","unstructured":"Edmonds, J., Ray Fulkerson, D.: Bottleneck extrema. J. Comb. Theory 8(3), 299\u2013306 (1970)","journal-title":"J. Comb. Theory"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N.: Parametric search and locating supply centers in trees. In: Algorithms and Data Structures, pp. 299\u2013319. Springer, Berlin (1991)","DOI":"10.1007\/BFb0028271"},{"key":"10_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)"},{"key":"10_CR13","unstructured":"Golovin, D., Gupta, A., Kumar, A., Tangwongsan, K., Hariharan, R., Mukund, M., Vinay, V.: All-norms and all-l_p-norms approximation algorithms. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, vol. 2, pp. 199\u2013210. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"key":"10_CR14","doi-asserted-by":"publisher","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."},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Zenklusen, R.: Approximation schemes for multi-budgeted independence systems. In: European Symposium on Algorithms, pp. 536\u2013548 (2010)","DOI":"10.1007\/978-3-642-15775-2_46"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Khandekar, R., Kortsarz, G.: Budgeted red\u2013blue median and its generalizations. In: European Symposium on Algorithms, pp. 314\u2013325 (2011)","DOI":"10.1007\/978-3-642-15775-2_27"},{"issue":"3","key":"10_CR17","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"D Hochbaum","year":"1986","unstructured":"Hochbaum, D., Shmoys, D.: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3), 533\u2013550 (1986)","journal-title":"J. ACM"},{"issue":"2","key":"10_CR18","doi-asserted-by":"publisher","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":"10_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)"},{"issue":"1","key":"10_CR20","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(98)00222-9","volume":"242","author":"S Khuller","year":"2000","unstructured":"Khuller, S., Pless, R., Sussmann, Y.J.: Fault tolerant k-center problems. Theor. Comput. Sci. 242(1), 237\u2013245 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Khuller, S., Saha, B., Sarpatwar, K.K.: New approximation results for resource replication problems. In: Approximation, Randomization, and Combinatorial Optimization, volume 7408 of LNCS, pp. 218\u2013230. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32512-0_19"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Krishnaswamy, R., Kumar, A., Nagarajan, V., Sabharwal, Y., Saha, B.: The matroid median problem. In: Proceedings of the Twenty-Second Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 1117\u20131130. SIAM (2011)","DOI":"10.1137\/1.9781611973082.84"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Kumar, A.: Constant factor approximation algorithm for the knapsack median problem. In: Proceedings of the Twenty-Third Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 824\u2013832. SIAM (2012)","DOI":"10.1137\/1.9781611973099.66"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, pp. 323\u2013332. ACM (2009)","DOI":"10.1145\/1536414.1536459"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Li, J., Yi, K., Zhang, Q.: Clustering with diversity. In: International Colloquium on Automata, Languages and Programming, pp. 188\u2013200. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-14165-2_17"},{"key":"10_CR26","unstructured":"McCutchen, R.M., Khuller, S.: Streaming algorithms for k-center clustering with outliers and with anonymity. In: Approximation, Randomization and Combinatorial Optimization, pp. 165\u2013178. Springer, Berlin (2008)"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 86\u201392. IEEE (2000)","DOI":"10.1109\/SFCS.2000.892068"},{"key":"10_CR28","unstructured":"Pisinger, D.: Algorithms for Knapsack Problems. PhD thesis, Department of Computer Science, University of Copenhagen (1995)"},{"key":"10_CR29","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"10_CR30","unstructured":"Swamy, C.: Improved approximation algorithms for matroid and knapsack median problems and applications. In: Approximation, Randomization and Combinatorial Optimization"},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J., Chekuri, C., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, pp. 783\u2013792. ACM (2011)","DOI":"10.1145\/1993636.1993740"},{"key":"10_CR32","unstructured":"Zarrabi-Zadeh, H., Mukhopadhyay, A.: Streaming 1-center with outliers in high dimensions. In: Canadian Conference on Computational Geometry, pp. 83\u201386 (2009)"},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"Zenklusen, R.: Matroidal degree-bounded minimum spanning trees. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1512\u20131521. SIAM (2012)","DOI":"10.1137\/1.9781611973099.120"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0010-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0010-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0010-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0010-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T23:34:53Z","timestamp":1748561693000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0010-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,12]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["10"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0010-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,12]]},"assertion":[{"value":"5 August 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}