{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:57:29Z","timestamp":1725479849699},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642366932"},{"type":"electronic","value":"9783642366949"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36694-9_10","type":"book-chapter","created":{"date-parts":[[2013,3,11]],"date-time":"2013-03-11T10:08:39Z","timestamp":1362996519000},"page":"110-122","source":"Crossref","is-referenced-by-count":2,"title":["Matroid and Knapsack Center Problems"],"prefix":"10.1007","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongyu","family":"Liang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Feder, T., Kenthapadi, K., Khuller, S., Panigrahy, R., Thomas, D., Zhu, A.: Achieving anonymity via clustering. In: PODS, pp. 153\u2013162 (2006)","DOI":"10.1145\/1142351.1142374"},{"key":"10_CR2","unstructured":"Charikar, M., Khuller, S., Mount, D., Narasimhan, G.: Algorithms for facility location problems with outliers. In: SODA, pp. 642\u2013651 (2001)"},{"key":"10_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-642-31594-7_17","volume-title":"Automata, Languages, and Programming","author":"M. Charikar","year":"2012","unstructured":"Charikar, M., Li, S.: A Dependent LP-Rounding Approach for the k-Median Problem. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 194\u2013205. Springer, Heidelberg (2012)"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-642-31104-8_2","volume-title":"Structural Information and Communication Complexity","author":"S. Chechik","year":"2012","unstructured":"Chechik, S., Peleg, D.: The Fault Tolerant Capacitated k-Center Problem. In: Even, G., Halld\u00f3rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol.\u00a07355, pp. 13\u201324. Springer, Heidelberg (2012)"},{"key":"10_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1007\/978-3-642-25591-5_60","volume-title":"Algorithms and Computation","author":"D.Z. Chen","year":"2011","unstructured":"Chen, D.Z., Wang, H.: Efficient Algorithms for the Weighted k-Center Problem on a Real Line. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 584\u2013593. Springer, Heidelberg (2011)"},{"key":"10_CR6","unstructured":"Chen, D.Z., Li, J., Liang, H., Wang, H.: Matroid and knapsack center problems. Technical report (2012), \n                  \n                    http:\/\/arxiv.org\/abs\/1301.0745"},{"key":"10_CR7","unstructured":"Chen, K.: A constant factor approximation algorithm for k-median clustering with outliers. In: SODA, pp. 826\u2013835 (2008)"},{"issue":"4","key":"10_CR8","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                n-hard to approximate. J. ACM\u00a052(4), 538\u2013551 (2005)","journal-title":"J. ACM"},{"issue":"1","key":"10_CR9","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\u00a034(1), 200\u2013208 (1987)","journal-title":"J. ACM"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Hajiaghayi, M., Khuller, S.: LP rounding for k-centers with non-uniform hard capacities. In: FOCS, pp. 273\u2013282 (2012)","DOI":"10.1109\/FOCS.2012.63"},{"issue":"3","key":"10_CR11","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., Fulkerson, D.: Bottleneck extrema. J. Combin. Theory\u00a08(3), 299\u2013306 (1970)","journal-title":"J. Combin. Theory"},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/BFb0028271","volume-title":"Algorithms and Data Structures","author":"G.N. Frederickson","year":"1991","unstructured":"Frederickson, G.N.: Parametric Search and Locating Supply Centers in Trees. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1991. LNCS, vol.\u00a0519, pp. 299\u2013319. Springer, Heidelberg (1991)"},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T. Gonzalez","year":"1985","unstructured":"Gonzalez, T.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci.\u00a038, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-642-15775-2_46","volume-title":"Algorithms \u2013 ESA 2010","author":"F. Grandoni","year":"2010","unstructured":"Grandoni, F., Zenklusen, R.: Approximation Schemes for Multi-Budgeted Independence Systems. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 536\u2013548. Springer, Heidelberg (2010)"},{"key":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/978-3-642-15775-2_27","volume-title":"Algorithms \u2013 ESA 2010","author":"M. Hajiaghayi","year":"2010","unstructured":"Hajiaghayi, M., Khandekar, R., Kortsarz, G.: Budgeted Red-Blue Median and Its Generalizations. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 314\u2013325. Springer, Heidelberg (2010)"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Hochbaum, D., Shmoys, D.: A best possible heuristic for the k-center problem. Math. Oper. Res., 180\u2013184 (1985)","DOI":"10.1287\/moor.10.2.180"},{"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\u00a033(3), 533\u2013550 (1986)","journal-title":"J. ACM"},{"issue":"1-2","key":"10_CR18","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.: Fault tolerant k-center problems. Theor. Comput. Sci.\u00a0242(1-2), 237\u2013245 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-642-32512-0_19","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Khuller","year":"2012","unstructured":"Khuller, S., Saha, B., Sarpatwar, K.K.: New Approximation Results for Resource Replication Problems. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM 2012. LNCS, vol.\u00a07408, pp. 218\u2013230. Springer, Heidelberg (2012)"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"Krishnaswamy, R., Kumar, A., Nagarajan, V., Sabharwal, Y., Saha, B.: The matroid median problem. In: SODA (2011)","DOI":"10.1137\/1.9781611973082.84"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Kumar, A.: Constant factor approximation algorithm for the knapsack median problem. In: SODA, pp. 824\u2013832 (2012)","DOI":"10.1137\/1.9781611973099.66"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: STOC, pp. 323\u2013332 (2009)","DOI":"10.1145\/1536414.1536459"},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-642-14165-2_17","volume-title":"Automata, Languages and Programming","author":"J. Li","year":"2010","unstructured":"Li, J., Yi, K., Zhang, Q.: Clustering with Diversity. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 188\u2013200. Springer, Heidelberg (2010)"},{"key":"10_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-540-85363-3_14","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"R. Matthew McCutchen","year":"2008","unstructured":"Matthew McCutchen, R., Khuller, S.: Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 165\u2013178. Springer, Heidelberg (2008)"},{"key":"10_CR25","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_CR26","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J., Chekuri, C., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: STOC, pp. 783\u2013792 (2011)","DOI":"10.1145\/1993636.1993740"},{"key":"10_CR27","unstructured":"Zarrabi-Zadeh, H., Mukhopadhyay, A.: Streaming 1-center with outliers in high dimensions. In: CCCG, pp. 83\u201386 (2009)"},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"Zenklusen, R.: Matroidal degree-bounded minimum spanning trees. In: SODA, pp. 1512\u20131521 (2012)","DOI":"10.1137\/1.9781611973099.120"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36694-9_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T17:47:19Z","timestamp":1557596839000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36694-9_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642366932","9783642366949"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36694-9_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}