{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T04:29:30Z","timestamp":1726892970818},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,3,14]],"date-time":"2022-03-14T00:00:00Z","timestamp":1647216000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,3,14]],"date-time":"2022-03-14T00:00:00Z","timestamp":1647216000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Sci. China Inf. Sci."],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s11432-021-3411-7","type":"journal-article","created":{"date-parts":[[2022,3,20]],"date-time":"2022-03-20T10:02:19Z","timestamp":1647770539000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An approximation algorithm for lower-bounded k-median with constant factor"],"prefix":"10.1007","volume":"65","author":[{"given":"Xiaoliang","family":"Wu","sequence":"first","affiliation":[]},{"given":"Feng","family":"Shi","sequence":"additional","affiliation":[]},{"given":"Yutian","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Zhen","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Junyu","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,14]]},"reference":[{"key":"3411_CR1","unstructured":"Ravishankar K, Li S, Sandeep S. Constant approximation for k-median and k-means with outliers via iterative rounding. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018. 646\u2013659"},{"key":"3411_CR2","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"D S Hochbaum","year":"1985","unstructured":"Hochbaum D S, Shmoys D B. A best possible heuristic for the k-center problem. Math Oper Res, 1985, 10: 180\u2013184","journal-title":"Math Oper Res"},{"key":"3411_CR3","doi-asserted-by":"publisher","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, 2016, 45: 530\u2013547","journal-title":"SIAM J Comput"},{"key":"3411_CR4","doi-asserted-by":"crossref","unstructured":"Chen D Z, Huang Z Y, Liu Y W, et al. On clustering induced Voronoi diagrams. In: Proceedings of the 54th Annual Symposium on Foundations of Computer Science, 2013. 390\u2013399","DOI":"10.1109\/FOCS.2013.49"},{"key":"3411_CR5","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"D S Hochbaum","year":"1986","unstructured":"Hochbaum D S, Shmoys D B. A unified approach to approximation algorithms for bottleneck problems. J ACM, 1986, 33: 533\u2013550","journal-title":"J ACM"},{"key":"3411_CR6","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/j.neucom.2021.04.028","volume":"450","author":"Z Zhang","year":"2021","unstructured":"Zhang Z, Feng Q L, Huang J Y, et al. A local search algorithm for k-means with outliers. Neurocomputing, 2021, 450: 230\u2013241","journal-title":"Neurocomputing"},{"key":"3411_CR7","doi-asserted-by":"publisher","first-page":"1091","DOI":"10.1007\/s10878-018-0340-4","volume":"37","author":"Q L Feng","year":"2019","unstructured":"Feng Q L, Hu J X, Huang N, et al. Improved PTAS for the constrained k-means problem. J Comb Optim, 2019, 37: 1091\u20131110","journal-title":"J Comb Optim"},{"key":"3411_CR8","first-page":"170","volume-title":"An improved approximation algorithm for the k-means problem with penalties","author":"Q L Feng","year":"2019","unstructured":"Feng Q L, Zhang Z, Shi F, et al. An improved approximation algorithm for the k-means problem with penalties. In: Proceedings of the 13th International Workshop on Frontiers in Algorithmics. Berlin: Springer, 2019. 170\u2013181"},{"key":"3411_CR9","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0020-0190(92)90208-D","volume":"44","author":"J H Lin","year":"1992","unstructured":"Lin J H, Vitter J S. Approximation algorithms for geometric median problems. Inf Process Lett, 1992, 44: 245\u2013249","journal-title":"Inf Process Lett"},{"key":"3411_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2981561","volume":"13","author":"J Byrka","year":"2017","unstructured":"Byrka J, Pensyl T, Rybicki B, et al. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans Algorithms, 2017, 13: 1\u201331","journal-title":"ACM Trans Algorithms"},{"key":"3411_CR11","doi-asserted-by":"publisher","first-page":"150104","DOI":"10.1007\/s11432-020-3066-x","volume":"64","author":"Z Zhang","year":"2021","unstructured":"Zhang Z, Feng Q L, Xu J H, et al. An approximation algorithm for k-median with priorities. Sci China Inf Sci, 2021, 64: 150104","journal-title":"Sci China Inf Sci"},{"key":"3411_CR12","doi-asserted-by":"crossref","unstructured":"Cohen-Addad V, Klein P N, Mathieu C. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. In: Proceedings of the 57th Annual Symposium on Foundations of Computer Science, 2016. 353\u2013364","DOI":"10.1109\/FOCS.2016.46"},{"key":"3411_CR13","doi-asserted-by":"publisher","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, 2001, 48: 274\u2013296","journal-title":"J ACM"},{"key":"3411_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1667053.1667054","volume":"57","author":"A Kumar","year":"2010","unstructured":"Kumar A, Sabharwal Y, Sen S. Linear-time approximation schemes for clustering problems in any dimensions. J ACM, 2010, 57: 1\u201332","journal-title":"J ACM"},{"key":"3411_CR15","doi-asserted-by":"crossref","unstructured":"Li S. Approximating capacitated k-median with (1 + \u03f5)k open facilities. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, 2016. 786\u2013796","DOI":"10.1137\/1.9781611974331.ch56"},{"key":"3411_CR16","unstructured":"Feng Q L, Zhang Z, Huang Z Y, et al. Improved algorithms for clustering with outliers. In: Proceedings of the 30th International Symposium on Algorithms and Computation, 2019. 1\u201312"},{"key":"3411_CR17","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1016\/j.future.2018.02.050","volume":"88","author":"L L Qi","year":"2018","unstructured":"Qi L L, Zhang X Y, Dou W C, et al. A two-stage locality-sensitive hashing based approach for privacy-preserving mobile service recommendation in cross-platform edge environment. Future Generation Comput Syst, 2018, 88: 636\u2013643","journal-title":"Future Generation Comput Syst"},{"key":"3411_CR18","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/j.ins.2018.11.030","volume":"480","author":"L Y Qi","year":"2019","unstructured":"Qi L Y, Wang R L, Hu C H, et al. Time-aware distributed service recommendation with privacy-preservation. Inf Sci, 2019, 480: 354\u2013364","journal-title":"Inf Sci"},{"key":"3411_CR19","doi-asserted-by":"crossref","unstructured":"Karger D R, Minkoff M. Building Steiner trees with incomplete global knowledge. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000. 613\u2013623","DOI":"10.1109\/SFCS.2000.892329"},{"key":"3411_CR20","doi-asserted-by":"crossref","unstructured":"Guha S, Meyerson A, Munagala K. Hierarchical placement and network design problems. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000. 603\u2013612","DOI":"10.1109\/SFCS.2000.892328"},{"key":"3411_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1824777.1824789","volume":"6","author":"Z Svitkina","year":"2010","unstructured":"Svitkina Z. Lower-bounded facility location. ACM Trans Algorithms, 2010, 6: 1\u201316","journal-title":"ACM Trans Algorithms"},{"key":"3411_CR22","doi-asserted-by":"crossref","unstructured":"Ahmadian S, Swamy C. Improved approximation guarantees for lower-bounded facility location. In: Proceedings of the 10th International Approximation and Online Algorithms Workshop, 2012. 257\u2013271","DOI":"10.1007\/978-3-642-38016-7_21"},{"key":"3411_CR23","doi-asserted-by":"crossref","unstructured":"Li S. On facility location with general lower bounds. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019. 2279\u20132290","DOI":"10.1137\/1.9781611975482.138"},{"key":"3411_CR24","doi-asserted-by":"crossref","unstructured":"Ding H, Xu J H. A unified framework for clustering constrained data without locality property. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 2015. 1471\u20131490","DOI":"10.1137\/1.9781611973730.97"},{"key":"3411_CR25","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00224-017-9820-7","volume":"62","author":"A Bhattacharya","year":"2018","unstructured":"Bhattacharya A, Jaiswal R, Kumar A. Faster algorithms for the constrained k-means problem. Theor Comput Syst, 2018, 62: 93\u2013115","journal-title":"Theor Comput Syst"},{"key":"3411_CR26","unstructured":"Ahmadian S, Swamy C. Approximation algorithms for clustering problems with lower bounds and outliers. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016. 1\u201315"},{"key":"3411_CR27","unstructured":"Feng Q L, Zhang Z, Huang Z Y, et al. A unified framework of FPT approximation algorithms for clustering problems. In: Proceedings of the 31st International Symposium on Algorithms and Computation, 2020. 1\u201317"},{"key":"3411_CR28","unstructured":"Demirci G, Li S. Constant approximation for capacitated k-median with (1+\u03f5)-capacity violation. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016. 1\u201314"},{"key":"3411_CR29","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, 2012. 194\u2013205","DOI":"10.1007\/978-3-642-31594-7_17"}],"container-title":["Science China Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-021-3411-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11432-021-3411-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-021-3411-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T16:56:21Z","timestamp":1726851381000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11432-021-3411-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,14]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["3411"],"URL":"https:\/\/doi.org\/10.1007\/s11432-021-3411-7","relation":{},"ISSN":["1674-733X","1869-1919"],"issn-type":[{"type":"print","value":"1674-733X"},{"type":"electronic","value":"1869-1919"}],"subject":[],"published":{"date-parts":[[2022,3,14]]},"assertion":[{"value":"12 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"140601"}}