{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:38Z","timestamp":1740122378815,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T00:00:00Z","timestamp":1624838400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T00:00:00Z","timestamp":1624838400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Beijing Natural Science Foundation Project","award":["Z200002"],"award-info":[{"award-number":["Z200002"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772005"],"award-info":[{"award-number":["61772005"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003392","name":"Natural Science Foundation of Fujian Province","doi-asserted-by":"crossref","award":["2017J01753"],"award-info":[{"award-number":["2017J01753"]}],"id":[{"id":"10.13039\/501100003392","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11701150"],"award-info":[{"award-number":["11701150"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s10878-021-00771-9","type":"journal-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T16:04:10Z","timestamp":1624896250000},"page":"2533-2550","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved local search algorithms for Bregman k-means and its variants"],"prefix":"10.1007","volume":"44","author":[{"given":"Xiaoyun","family":"Tian","sequence":"first","affiliation":[]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2891-4253","authenticated-orcid":false,"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Dan","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,28]]},"reference":[{"key":"771_CR1","doi-asserted-by":"crossref","unstructured":"Ackermann M Bl\u00f6mer J (2009) Coresets and approximate clustering for Bregman divergences. In: Proceedings of SODA, pp 1088\u20131097","DOI":"10.1137\/1.9781611973068.118"},{"key":"771_CR2","doi-asserted-by":"crossref","unstructured":"Ackermann M, Bl\u00f6mer J (2010) Bregman clustering for separable instances. In: Proceedings of SWAT, pp 212\u2013223","DOI":"10.1007\/978-3-642-13731-0_21"},{"issue":"4","key":"771_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1824777.1824779","volume":"6","author":"M Ackermann","year":"2010","unstructured":"Ackermann M, Bl\u00f6mer J, Sohler C (2010) Clustering for metric and non-metric distance measures. ACM Trans Algorithms 6(4):1\u201359","journal-title":"ACM Trans Algorithms"},{"key":"771_CR4","unstructured":"Arthur D, Vassilvitskii S (2007) $$k$$-means++: the advantages of careful seeding. In: Proceedings of SODA, pp 1027\u20131035"},{"issue":"7","key":"771_CR5","doi-asserted-by":"publisher","first-page":"2664","DOI":"10.1109\/TIT.2005.850145","volume":"51","author":"A Banerjee","year":"2005","unstructured":"Banerjee A, Guo X, Wang H (2005) On the optimality of conditional expectation as a Bregman predictor. IEEE Trans Inf Theory 51(7):2664\u20132669","journal-title":"IEEE Trans Inf Theory"},{"key":"771_CR6","first-page":"1705","volume":"6","author":"A Banerjee","year":"2005","unstructured":"Banerjee A, Merugu S, Dhillon I, Ghosh J (2005) Clustering with Bregman divergences. J Mach Learn Res 6:1705\u20131749","journal-title":"J Mach Learn Res"},{"issue":"3","key":"771_CR7","doi-asserted-by":"publisher","first-page":"317","DOI":"10.26599\/TST.2018.9010087","volume":"24","author":"A Belhassena","year":"2019","unstructured":"Belhassena A, Wang H (2019) Trajectory big data processing based on frequent activity. Tsinghua Sci Technol 24(3):317\u2013332","journal-title":"Tsinghua Sci Technol"},{"key":"771_CR8","unstructured":"Bhattacharya A, Eube J, Heiko R\u00f6glin H, Schmidt MN (2020) Greedy and Not So Greedy $$k$$-means++. In: Proceedings of ESA, pp 18:1-18:21"},{"key":"771_CR9","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/0041-5553(67)90040-7","volume":"7","author":"L Bregman","year":"1967","unstructured":"Bregman L (1967) The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming. USSR Comput Math Math Phys 7:200\u2013217","journal-title":"USSR Comput Math Math Phys"},{"issue":"3","key":"771_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF00934676","volume":"34","author":"Y Censor","year":"1981","unstructured":"Censor Y, Lent A (1981) An iterative rowaction method for interval convex programming. J Optim Theory Appl 34(3):321\u2013353","journal-title":"J Optim Theory Appl"},{"key":"771_CR11","unstructured":"Choo D, Grunau C, Portmann J, Rozhon V (2020) $$k$$-means++: few more steps yield constant approximation In: Proceedings of the 37th International Conference on Machine Learning (ICML), pp 1909\u20131917"},{"key":"771_CR12","volume-title":"Parallel optimization: theory, algorithms, and applications","author":"Y Censor","year":"1997","unstructured":"Censor Y, Zenios S (1997) Parallel optimization: theory, algorithms, and applications. Oxford University Press, Oxford"},{"issue":"3","key":"771_CR13","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/18M1209854","volume":"49","author":"D Feldman","year":"2020","unstructured":"Feldman D, Schmidt M, Sohler C (2020) Turning big data into tiny data: constant-size coresets for $$k$$-means, PCA and projective clustering. SIAM J Comput 49(3):601\u2013657","journal-title":"SIAM J Comput"},{"key":"771_CR14","volume-title":"Algorithms for clustering data","author":"A Jain","year":"1988","unstructured":"Jain A, Dubes R (1988) Algorithms for clustering data. Prentice Hall, New Jersey"},{"key":"771_CR15","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1145\/331499.331504","volume":"31","author":"A Jain","year":"1999","unstructured":"Jain A, Murty M, Flynn P (1999) Data clustering: a review. ACM Comput Surveys 31:264\u2013323","journal-title":"ACM Comput Surveys"},{"key":"771_CR16","doi-asserted-by":"crossref","unstructured":"Kanungo T, Mount D, Netanyahu N, Piatko C, Silverman R, Wu A (2002) A local search approximation algorithm for $$k$$-means clustering. In: Proceedings of SoCG, pp 10\u201318","DOI":"10.1145\/513400.513402"},{"key":"771_CR17","unstructured":"Kumar A, Sabharwal Y, Sen S. A simple linear time $$(1+\\varepsilon )$$-approximation algorithm for $$k$$-means clustering in any dimensions. In: Proceedings of FOCS, pp 454\u2013462"},{"key":"771_CR18","unstructured":"Lattanzi S, Sohler C (2019) A better $$k$$-means++ algorithm via local search. In: Proceedings of ICML, pp 3662\u20133671"},{"issue":"2","key":"771_CR19","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd S (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129\u2013137","journal-title":"IEEE Trans Inf Theory"},{"issue":"6","key":"771_CR20","doi-asserted-by":"publisher","first-page":"813","DOI":"10.26599\/TST.2020.9010007","volume":"25","author":"N Wang","year":"2020","unstructured":"Wang N, Guo G, Wang B, Wang C (2020) Traffic clustering algorithm of urban data brain based on a hybrid-augmented architecture of quantum annealing and brain-inspired cognitive computing. Tsinghua Sci Technol 25(6):813\u2013825","journal-title":"Tsinghua Sci Technol"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00771-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00771-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00771-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:20:31Z","timestamp":1665778831000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00771-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,28]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["771"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00771-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,6,28]]},"assertion":[{"value":"9 June 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}