{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T11:45:34Z","timestamp":1747482334217,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T00:00:00Z","timestamp":1532995200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Russian Foundation for Basic Research","award":["16-07-00266","16-01-00505"],"award-info":[{"award-number":["16-07-00266","16-01-00505"]}]},{"name":"Russian Foundation for Basic Research","award":["17-08-01385"],"award-info":[{"award-number":["17-08-01385"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2019,11]]},"DOI":"10.1007\/s11590-018-1305-3","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T09:41:52Z","timestamp":1533030112000},"page":"1837-1853","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Attainable accuracy guarantee for the k-medians clustering in [0,\u00a01]"],"prefix":"10.1007","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3555-0080","authenticated-orcid":false,"given":"Michael","family":"Khachay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9276-4128","authenticated-orcid":false,"given":"Daniel","family":"Khachay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,31]]},"reference":[{"key":"1305_CR1","unstructured":"Abbey, R., Diepenbrock, J., Langville, A.N., Meyer, C.D., Race, S., Zhou, D.: Data clustering via principal direction gap partitioning. CoRR \n                    arXiv:1211.4142\n                    \n                   (2012)"},{"key":"1305_CR2","doi-asserted-by":"publisher","DOI":"10.1201\/b15410","volume-title":"Data Clustering: Algorithms and Applications","author":"CC Aggarwal","year":"2013","unstructured":"Aggarwal, C.C., Reddy, C.K.: Data Clustering: Algorithms and Applications, 1st edn. Chapman & Hall\/CRC, Boca Raton (2013)","edition":"1"},{"issue":"1","key":"1305_CR3","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s10107-013-0729-x","volume":"147","author":"BPW Ames","year":"2014","unstructured":"Ames, B.P.W.: Guaranteed clustering and biclustering via semidefinite programming. Math. Program. 147(1), 429\u2013465 (2014). \n                    https:\/\/doi.org\/10.1007\/s10107-013-0729-x","journal-title":"Math. Program."},{"issue":"4","key":"1305_CR4","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1023\/A:1009740529316","volume":"2","author":"D Boley","year":"1998","unstructured":"Boley, D.: Principal direction divisive partitioning. Data Min. Knowl. Discov. 2(4), 325\u2013344 (1998). \n                    https:\/\/doi.org\/10.1023\/A:1009740529316","journal-title":"Data Min. Knowl. Discov."},{"issue":"3","key":"1305_CR5","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/1970392.1970395","volume":"58","author":"EJ Cand\u00e8s","year":"2011","unstructured":"Cand\u00e8s, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. ACM 58(3), 11:1\u201311:37 (2011). \n                    https:\/\/doi.org\/10.1145\/1970392.1970395","journal-title":"J. ACM"},{"key":"1305_CR6","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/3-540-45435-7_24","volume-title":"Computational Learning Theory","author":"S Dasgupta","year":"2002","unstructured":"Dasgupta, S.: Performance guarantees for hierarchical clustering. In: Kivinen, J., Sloan, R.H. (eds.) Computational Learning Theory, pp. 351\u2013363. Springer, Berlin (2002)"},{"key":"1305_CR7","doi-asserted-by":"publisher","unstructured":"de\u00a0Berg, M., Buchin, K., Jansen, B.M.P., Woeginger, G.: Fine-grained complexity analysis of two classic TSP variants. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a055, pp. 5:1\u20135:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). \n                    https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.5\n                    \n                  , \n                    http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2016\/6277","DOI":"10.4230\/LIPIcs.ICALP.2016.5"},{"key":"1305_CR8","volume-title":"Pattern Classification","author":"RO Duda","year":"2001","unstructured":"Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification, 2nd edn. Wiley, Hoboken (2001)","edition":"2"},{"issue":"1\u20133","key":"1305_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0166-218X(98)00048-1","volume":"87","author":"H Enomoto","year":"1998","unstructured":"Enomoto, H., Oda, Y., Ota, K.: Pyramidal tours with step-backs and the asymmetric traveling salesman problem. Discrete Appl. Math. 87(1\u20133), 57\u201365 (1998). \n                    https:\/\/doi.org\/10.1016\/S0166-218X(98)00048-1","journal-title":"Discrete Appl. Math."},{"key":"1305_CR10","series-title":"Inverse and Ill-Posed Problems","volume-title":"Theory of Linear Optimization","author":"I Eremin","year":"2002","unstructured":"Eremin, I.: Theory of Linear Optimization. Inverse and Ill-Posed Problems, vol. 29. VSP, Utrecht (2002)"},{"key":"1305_CR11","unstructured":"Gr\u00f8nlund, A., Larsen, K.G., Mathiasen, A., Nielsen, J.S.: Fast exact k-means, k-medians and Bregman divergence clustering in 1D. CoRR \n                    arXiv:1701.07204\n                    \n                   (2017)"},{"key":"1305_CR12","unstructured":"Guruswami, V., Indyk, P.: Embeddings and non-approximability of geometric problems. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201903, pp. 537\u2013538. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. \n                    http:\/\/dl.acm.org\/citation.cfm?id=644108.644198\n                    \n                   (2003)"},{"key":"1305_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/b101971","volume-title":"The Traveling Salesman Problem and Its Variations","author":"G Gutin","year":"2007","unstructured":"Gutin, G., Punnen, A.P.: The Traveling Salesman Problem and Its Variations. Springer, Boston (2007)"},{"key":"1305_CR14","doi-asserted-by":"publisher","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC \u201904, pp. 291\u2013300. ACM, New York, NY, USA (2004). \n                    https:\/\/doi.org\/10.1145\/1007352.1007400","DOI":"10.1145\/1007352.1007400"},{"key":"1305_CR15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-319-71150-8-23","volume-title":"Generalized Pyramidal Tours for the Generalized Traveling Salesman Problem","author":"M Khachay","year":"2017","unstructured":"Khachay, M., Neznakhina, K.: Generalized Pyramidal Tours for the Generalized Traveling Salesman Problem. LNCS, vol. 10627, pp. 265\u2013277. Springer, Cham (2017). \n                    https:\/\/doi.org\/10.1007\/978-3-319-71150-8-23"},{"key":"1305_CR16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/978-3-319-73013-4_32","volume-title":"Polynomial Time Solvable Subclass of the Generalized Traveling Salesman Problem on Grid Clusters","author":"M Khachay","year":"2018","unstructured":"Khachay, M., Neznakhina, K.: Polynomial Time Solvable Subclass of the Generalized Traveling Salesman Problem on Grid Clusters. LNCS, vol. 10716, pp. 346\u2013355. Springer, Cham (2018). \n                    https:\/\/doi.org\/10.1007\/978-3-319-73013-4_32"},{"key":"1305_CR17","unstructured":"Khachay, M., Pankratov, V., Khachay, D.: Attainable best guarantee for the accuracy of k-medians clustering in [0, 1]. In: Optimization and Applications (OPTIMA2017), pp. 322\u2013327. \n                    http:\/\/ceur-ws.org\/Vol-1987\/paper-47.pdf\n                    \n                   (2017)"},{"key":"1305_CR18","unstructured":"Klyaus, P.: Generation of testproblems for the traveling salesman problem. Preprint Inst. Mat. Akad. Nauk. BSSR (16) (1976) (in Russian)"},{"issue":"3","key":"1305_CR19","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/s00357-015-9186-y","volume":"32","author":"EV Kovaleva","year":"2015","unstructured":"Kovaleva, E.V., Mirkin, B.G.: Bisecting k-means and 1D projection divisive clustering: a unified framework and experimental comparison. J. Classif. 32(3), 414\u2013442 (2015). \n                    https:\/\/doi.org\/10.1007\/s00357-015-9186-y","journal-title":"J. Classif."},{"issue":"2","key":"1305_CR20","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.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM 57(2), 5:1\u20135:32 (2010). \n                    https:\/\/doi.org\/10.1145\/1667053.1667054","journal-title":"J. ACM"},{"issue":"4","key":"1305_CR21","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1023\/A:1020443310743","volume":"5","author":"M Nilsson","year":"2002","unstructured":"Nilsson, M.: Hierarchical clustering using non-greedy principal direction divisive partitioning. Inf. Retr. 5(4), 311\u2013321 (2002). \n                    https:\/\/doi.org\/10.1023\/A:1020443310743","journal-title":"Inf. Retr."},{"issue":"1","key":"1305_CR22","doi-asserted-by":"publisher","first-page":"123","DOI":"10.4036\/iis.2001.123","volume":"7","author":"Y Oda","year":"2001","unstructured":"Oda, Y., Ota, K.: Algorithmic aspects of pyramidal tours with restricted jump-backs. Interdiscip. Inf. Sci. 7(1), 123\u2013133 (2001). \n                    https:\/\/doi.org\/10.4036\/iis.2001.123","journal-title":"Interdiscip. Inf. Sci."},{"issue":"1","key":"1305_CR23","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s11590-011-0389-9","volume":"7","author":"K Sabo","year":"2013","unstructured":"Sabo, K., Scitovski, R., Vazler, I.: One-dimensional center-based \n                    \n                      \n                    \n                    $$l_1$$\n                    \n                      \n                        \n                          l\n                          1\n                        \n                      \n                    \n                  -clustering method. Optim. Lett. 7(1), 5\u201322 (2013). \n                    https:\/\/doi.org\/10.1007\/s11590-011-0389-9","journal-title":"Optim. Lett."},{"key":"1305_CR24","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, London (1998)"},{"issue":"10","key":"1305_CR25","doi-asserted-by":"publisher","first-page":"3391","DOI":"10.1016\/j.patcog.2010.05.025","volume":"43","author":"S Tasoulis","year":"2010","unstructured":"Tasoulis, S., Tasoulis, D., Plagianakos, V.: Enhancing principal direction divisive clustering. Pattern Recognit. 43(10), 3391\u20133411 (2010). \n                    https:\/\/doi.org\/10.1016\/j.patcog.2010.05.025","journal-title":"Pattern Recognit."},{"key":"1305_CR26","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-1-84800-046-9_3","volume-title":"Survey of Text Mining II","author":"Dimitrios Zeimpekis","year":"2008","unstructured":"Zeimpekis, D., Gallopoulos, E.: Principal direction divisive partitioning with kernels and k-means steering (2008). \n                    https:\/\/doi.org\/10.1007\/978-1-84800-046-9_3"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-018-1305-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-018-1305-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-018-1305-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T22:37:26Z","timestamp":1589927846000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-018-1305-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,31]]},"references-count":26,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["1305"],"URL":"https:\/\/doi.org\/10.1007\/s11590-018-1305-3","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2018,7,31]]},"assertion":[{"value":"30 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}