{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:43Z","timestamp":1759638343473,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,8,23]],"date-time":"2018-08-23T00:00:00Z","timestamp":1534982400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61420106009"],"award-info":[{"award-number":["61420106009"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s10878-018-0340-4","type":"journal-article","created":{"date-parts":[[2018,8,23]],"date-time":"2018-08-23T07:29:21Z","timestamp":1535009361000},"page":"1091-1110","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Improved PTAS for the constrained k-means problem"],"prefix":"10.1007","volume":"37","author":[{"given":"Qilong","family":"Feng","sequence":"first","affiliation":[]},{"given":"Jiaxin","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Neng","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,23]]},"reference":[{"issue":"3","key":"340_CR1","doi-asserted-by":"publisher","first-page":"49:1","DOI":"10.1145\/1798596.1798602","volume":"6","author":"G Aggarwal","year":"2010","unstructured":"Aggarwal G, Panigrahy R, Feder T, Thomas D, Kenthapadi K, Khuller S, Zhu A (2010) Achieving anonymity via clustering. ACM Trans Algorithms 6(3):49:1\u201349:19","journal-title":"ACM Trans Algorithms"},{"key":"340_CR2","doi-asserted-by":"crossref","unstructured":"Ahmadian S, Norouzi-Fard A, Svensson O, Ward J (2017) Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. In: Proceedings of 58th annual symposium on foundations of computer science, FOCS, California, USA, pp 61\u201372","DOI":"10.1109\/FOCS.2017.15"},{"issue":"2","key":"340_CR3","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"Aloise D, Deshpande A, Hansen P, Popat P (2009) NP-hardness of euclidean sum-of-squares clustering. Mach Learn 75(2):245\u2013248","journal-title":"Mach Learn"},{"key":"340_CR4","unstructured":"Arthur D, Vassilvitskii S (2007) k-means++: the advantages of careful seeding. In: Proceedings of 18th annual ACM-SIAM symposium on discrete algorithms, SODA, Louisiana, USA, pp 1027\u20131035"},{"key":"340_CR5","unstructured":"Awasthi P, Charikar M, Krishnaswamy R, Sinop AK (2015) The hardness of approximation of Euclidean k-means. In: Proceedings of 31st annual international symposium on computational geometry, SoCG, Eindhoven, The Netherlands, pp 754\u2013767"},{"key":"340_CR6","doi-asserted-by":"crossref","unstructured":"Badoiu M, Har-Peled S, Indyk P (2002) Approximate clustering via core-sets. In: Proceedings of 34th annual ACM symposium on theory of computing, STOC, Qu\u00e9bec, Canada, pp 250\u2013257","DOI":"10.1145\/509907.509947"},{"issue":"2","key":"340_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.ic.2009.10.001","volume":"208","author":"N Betzler","year":"2010","unstructured":"Betzler N, Guo J, Niedermeier R (2010) Parameterized computational complexity of dodgson and young elections. Inf Comput 208(2):165\u2013177","journal-title":"Inf Comput"},{"key":"340_CR8","unstructured":"Bhattacharya A, Jaiswal R, Kumar A (2016) Faster algorithms for the constrained k-means problem. In: Proceedings of 33rd annual symposium on theoretical aspects of computer science, STACS, Orl\u00e9ans, France, pp 16:1\u201316:13"},{"issue":"1","key":"340_CR9","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 (2018) Faster algorithms for the constrained k-means problem. Theory Comput Syst 62(1):93\u2013115","journal-title":"Theory Comput Syst"},{"key":"340_CR10","doi-asserted-by":"crossref","unstructured":"Cabello S, Giannopoulos P, Knauer C, Marx D, Rote G (2011) Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. ACM Trans Algorithms 7(4):43:1\u201343:27","DOI":"10.1145\/2000807.2000811"},{"key":"340_CR11","doi-asserted-by":"crossref","unstructured":"Cohen-Addad V (2018) A fast approximation scheme for low-dimensional k-means. In: Proceedings 29th annual ACM-SIAM symposium on discrete algorithms, SODA, Louisiana, USA, pp 430\u2013440","DOI":"10.1137\/1.9781611975031.29"},{"key":"340_CR12","doi-asserted-by":"crossref","unstructured":"Cohen-Addad V, Klein PN, Mathieu C (2016) Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. In: Proceedings of 57th annual symposium on foundations of computer science, FOCS, New Jersey, USA, pp 353\u2013364","DOI":"10.1109\/FOCS.2016.46"},{"key":"340_CR13","doi-asserted-by":"crossref","unstructured":"Cygan M, Hajiaghayi M, Khuller S (2012) LP rounding for k-centers with non-uniform hard capacities. In: Proceedings of 53rd annual symposium on foundations of computer science, FOCS, New Jersey, USA, pp 273\u2013282","DOI":"10.1109\/FOCS.2012.63"},{"key":"340_CR14","doi-asserted-by":"crossref","unstructured":"Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer","DOI":"10.1007\/978-3-319-21275-3"},{"key":"340_CR15","doi-asserted-by":"crossref","unstructured":"De\u00a0la Vega WF, Karpinski M, Kenyon C, Rabani Y (2003) Approximation schemes for clustering problems. In: Proceedings of 35th annual ACM symposium on theory of computing, STOC, California, USA, pp 50\u201358","DOI":"10.1145\/780542.780550"},{"key":"340_CR16","doi-asserted-by":"crossref","unstructured":"Ding H, Xu J (2011) Solving the chromatic cone clustering problem via minimum spanning sphere. In: Proceedings of 38th annual international colloquium on automata, languages and programming, ICALP, Zurich, Switzerland, pp 773\u2013784","DOI":"10.1007\/978-3-642-22006-7_65"},{"key":"340_CR17","doi-asserted-by":"crossref","unstructured":"Ding H, Xu J (2015) A unified framework for clustering constrained data without locality property. In: Proceedings of 26th annual ACM-SIAM symposium on discrete algorithms, SODA, California, USA, pp 1471\u20131490","DOI":"10.1137\/1.9781611973730.97"},{"key":"340_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey RG, Fellows MR (1999) Parameterized complexity. Monographs in computer science, Springer"},{"key":"340_CR19","unstructured":"Ene A, Har-Peled S, Raichel B (2013) Fast clustering with lower bounds: no customer too far, no shop too small. CoRR \n                    arXiv:1304.7318"},{"volume-title":"Advances in knowledge discovery and data mining","year":"1996","key":"340_CR20","unstructured":"Fayyad UM, Piatetsky-Shapiro G, Smyth P, Uthurusamy R (eds) (1996) Advances in knowledge discovery and data mining. AAAI Press, Quebec"},{"key":"340_CR21","doi-asserted-by":"crossref","unstructured":"Feldman D, Monemizadeh M, Sohler C (2007) A PTAS for k-means clustering based on weak coresets. In: Proceedings of 23rd annual ACM symposium on computational geometry, SoCG, Gyeongju, South Korea, pp 11\u201318","DOI":"10.1145\/1247069.1247072"},{"key":"340_CR22","doi-asserted-by":"crossref","unstructured":"Feldman D, Schmidt M, Sohler C (2013) Turning big data into tiny data: constant-size coresets for k-means, PCA and projective clustering. In: Proceedings of 24th annual ACM-SIAM symposium on discrete algorithms, SODA, Louisiana, USA, pp 1434\u20131453","DOI":"10.1137\/1.9781611973105.103"},{"key":"340_CR23","doi-asserted-by":"crossref","unstructured":"Feldmann AE (2015) Fixed parameter approximations for \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -center problems in low highway dimension graphs. In: Proceedings of 42th annual international colloquium on automata, languages and programming, ICALP, Kyoto, Japan, pp 588\u2013600","DOI":"10.1007\/978-3-662-47666-6_47"},{"key":"340_CR24","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.tcs.2017.09.024","volume":"734","author":"Q Feng","year":"2018","unstructured":"Feng Q, Huang N, Jiang X, Wang J (2018a) Dealing with several parameterized problems by random methods. Theor Comput Sci 734:94\u2013104","journal-title":"Theor Comput Sci"},{"key":"340_CR25","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.tcs.2017.09.027","volume":"734","author":"Q Feng","year":"2018","unstructured":"Feng Q, Li S, Zhou Z, Wang J (2018b) Parameterized algorithms for edge biclique and related problems. Theor Comput Sci 734:105\u2013118","journal-title":"Theor Comput Sci"},{"key":"340_CR26","doi-asserted-by":"crossref","unstructured":"Friggstad Z, Rezapour M, Salavatipour MR (2016) Local search yields a PTAS for k-means in doubling metrics. In: Proceedings of 57th annual symposium on foundations of computer science, FOCS, New Jersey, USA, pp 365\u2013374","DOI":"10.1109\/FOCS.2016.47"},{"key":"340_CR27","doi-asserted-by":"publisher","unstructured":"Gao J, Ping Q, Wang J (2018) Resisting re-identification mining on social graph data. World Wide Web. \n                    https:\/\/doi.org\/10.1007\/s11280-017-0524-3","DOI":"10.1007\/s11280-017-0524-3"},{"issue":"12","key":"340_CR28","doi-asserted-by":"publisher","first-page":"3320","DOI":"10.1109\/TMC.2017.2696009","volume":"16","author":"L Guo","year":"2017","unstructured":"Guo L, Shen H, Zhu W (2017) Efficient approximation algorithms for multi-antennae largest weight data retrieval. IEEE Trans Mob Comput 16(12):3320\u20133333","journal-title":"IEEE Trans Mob Comput"},{"issue":"3","key":"340_CR29","doi-asserted-by":"publisher","first-page":"36:1","DOI":"10.1145\/2854153","volume":"12","author":"MT Hajiaghayi","year":"2016","unstructured":"Hajiaghayi MT, Hu W, Li J, Li S, Saha B (2016) A constant factor approximation algorithm for fault-tolerant k-median. ACM Trans Algorithms 12(3):36:1\u201336:19","journal-title":"ACM Trans Algorithms"},{"issue":"6","key":"340_CR30","doi-asserted-by":"publisher","first-page":"44:1","DOI":"10.1145\/2831230","volume":"62","author":"S Har-Peled","year":"2015","unstructured":"Har-Peled S, Raichel B (2015) Net and prune: a linear time algorithm for Euclidean distance problems. J ACM 62(6):44:1\u201344:35","journal-title":"J ACM"},{"issue":"301","key":"340_CR31","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J Am Stat Assoc 58(301):13\u201330","journal-title":"J Am Stat Assoc"},{"key":"340_CR32","unstructured":"Inaba M, Katoh N, Imai H (1994) Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering (extended abstract). In: Proceedings of 10th annual symposium on computational geometry, SoCG, New York, USA, pp 332\u2013339"},{"issue":"3","key":"340_CR33","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1145\/331499.331504","volume":"31","author":"AK Jain","year":"1999","unstructured":"Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM Comput Surv 31(3):264\u2013323","journal-title":"ACM Comput Surv"},{"issue":"1","key":"340_CR34","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/34.824819","volume":"22","author":"AK Jain","year":"2000","unstructured":"Jain AK, Duin RPW, Mao J (2000) Statistical pattern recognition: a review. IEEE Trans Pattern Anal Mach Intell 22(1):4\u201337","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"2","key":"340_CR35","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.ipl.2014.07.009","volume":"115","author":"R Jaiswal","year":"2015","unstructured":"Jaiswal R, Kumar M, Yadav P (2015) Improved analysis of D\n                    \n                      \n                    \n                    $${}^{2}$$\n                    \n                      \n                        \n                          \n                          2\n                        \n                      \n                    \n                  -sampling based PTAS for k-means and other clustering problems. Inf Process Lett 115(2):100\u2013103","journal-title":"Inf Process Lett"},{"issue":"2\u20133","key":"340_CR36","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.comgeo.2004.03.003","volume":"28","author":"T Kanungo","year":"2004","unstructured":"Kanungo T, Mount DM, Netanyahu NS, Piatko CD, Silverman R, Wu AY (2004) A local search approximation algorithm for k-means clustering. Comput Geom 28(2\u20133):89\u2013112","journal-title":"Comput Geom"},{"issue":"3","key":"340_CR37","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/S0895480197329776","volume":"13","author":"S Khuller","year":"2000","unstructured":"Khuller S, Sussmann YJ (2000) The capacitated K-center problem. SIAM J Discrete Math 13(3):403\u2013418","journal-title":"SIAM J Discrete Math"},{"issue":"1\u20132","key":"340_CR38","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 YJ (2000) Fault tolerant K-center problems. Theor Comput Sci 242(1\u20132):237\u2013245","journal-title":"Theor Comput Sci"},{"issue":"2","key":"340_CR39","doi-asserted-by":"publisher","first-page":"5:1","DOI":"10.1145\/1667053.1667054","volume":"57","author":"A Kumar","year":"2010","unstructured":"Kumar A, Sabharwal Y, Sen S (2010) Linear-time approximation schemes for clustering problems in any dimensions. J ACM 57(2):5:1\u20135:32","journal-title":"J ACM"},{"key":"340_CR40","unstructured":"Kumar N, Raichel B (2013) Fault tolerant clustering revisited. In: Proceedings of 25th annual Canadian conference on computational geometry, CCCG, Ontario, Canada"},{"key":"340_CR41","doi-asserted-by":"crossref","unstructured":"Li J, Yi K, Zhang Q (2010) Clustering with diversity. In: Proceedings of 37th annual international colloquium on automata, languages and programming, ICALP, Bordeaux, France, pp 188\u2013200","DOI":"10.1007\/978-3-642-14165-2_17"},{"key":"340_CR42","doi-asserted-by":"crossref","unstructured":"Li W, Feng Q, Chen J, Hu S (2017) Improved kernel results for some FPT problems based on simple observations. Theor Comput Sci 657:20\u201327","DOI":"10.1016\/j.tcs.2016.06.012"},{"key":"340_CR43","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.tcs.2016.06.044","volume":"657","author":"M Lin","year":"2017","unstructured":"Lin M, Feng Q, Chen J, Li W (2017) Partition on trees with supply and demand: Kernelization and algorithms. Theor Comput Sci 657:11\u201319","journal-title":"Theor Comput Sci"},{"key":"340_CR44","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.ipl.2018.03.016","volume":"136","author":"M Lin","year":"2018","unstructured":"Lin M, Feng Q, Wang J, Chen J, Fu B, Li W (2018) An improved FPT algorithm for almost forest deletion problem. Inf Process Lett 136:30\u201336","journal-title":"Inf Process Lett"},{"issue":"2","key":"340_CR45","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"SP Lloyd","year":"1982","unstructured":"Lloyd SP (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129\u2013136","journal-title":"IEEE Trans Inf Theory"},{"key":"340_CR46","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2010.05.034","volume":"442","author":"M Mahajan","year":"2012","unstructured":"Mahajan M, Nimbhorkar P, Varadarajan KR (2012) The planar k-means problem is NP-hard. Theor Comput Sci 442:13\u201321","journal-title":"Theor Comput Sci"},{"issue":"6","key":"340_CR47","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/2395116.2395117","volume":"59","author":"R Ostrovsky","year":"2012","unstructured":"Ostrovsky R, Rabani Y, Schulman LJ, Swamy C (2012) The effectiveness of lloyd-type methods for the k-means problem. J ACM 59(6):28:1\u201328:22","journal-title":"J ACM"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0340-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0340-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0340-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,22]],"date-time":"2019-08-22T19:13:47Z","timestamp":1566501227000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0340-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,23]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["340"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0340-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,8,23]]},"assertion":[{"value":"23 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}