{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T19:00:25Z","timestamp":1743102025803,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319529196"},{"type":"electronic","value":"9783319529202"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-52920-2_5","type":"book-chapter","created":{"date-parts":[[2017,2,16]],"date-time":"2017-02-16T13:13:40Z","timestamp":1487250820000},"page":"51-57","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Complexity of Searching a Subset of Vectors with Shortest Average Under a Cardinality Restriction"],"prefix":"10.1007","author":[{"given":"Anton V.","family":"Eremeev","sequence":"first","affiliation":[]},{"given":"Alexander V.","family":"Kel\u2019manov","sequence":"additional","affiliation":[]},{"given":"Artem V.","family":"Pyatkin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,17]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-14142-8","volume-title":"Data Mining: The Textbook","author":"CC Aggarwal","year":"2015","unstructured":"Aggarwal, C.C.: Data Mining: The Textbook. Springer International Publishing, Switzerland (2015)"},{"key":"5_CR2","volume-title":"Pattern Recognition and Machine Learning","author":"MC Bishop","year":"2006","unstructured":"Bishop, M.C.: Pattern Recognition and Machine Learning. Springer Science+Business Media, LLC, New York (2006)"},{"issue":"1","key":"5_CR3","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1134\/S1990478908010043","volume":"2","author":"AE Baburin","year":"2008","unstructured":"Baburin, A.E., Gimadi, E.K., Glebov, N.I., Pyatkin, A.V.: The problem of finding a subset of vectors with the maximum total weight. J. Appl. Ind. Math. 2(1), 32\u201338 (2008)","journal-title":"J. Appl. Ind. Math."},{"key":"5_CR4","series-title":"Energy Systems","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-540-88965-6_3","volume-title":"Optimization in the Energy Industry","author":"PA Borisovsky","year":"2009","unstructured":"Borisovsky, P.A., Eremeev, A.V., Grinkevich, E.B., Klokov, S.A., Vinnikov, A.V.: Trading hubs construction for electricity markets. In: Kallrath, J., Pardalos, P.M., Rebennack, S., Scheidt, M. (eds.) Optimization in the Energy Industry. Energy Systems, pp. 29\u201358. Springer, Heidelberg (2009)"},{"issue":"4","key":"5_CR5","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1134\/S1990478911040107","volume":"5","author":"AV Dolgushev","year":"2011","unstructured":"Dolgushev, A.V., Kel\u2019manov, A.V.: An approximation algorithm for solving a problem of cluster analysis. J. Appl. Ind. Math. 5(4), 551\u2013558 (2011)","journal-title":"J. Appl. Ind. Math."},{"issue":"3","key":"5_CR6","first-page":"100","volume":"21","author":"AV Dolgushev","year":"2015","unstructured":"Dolgushev, A.V., Kel\u2019manov, A.V., Shenmaier, V.V.: Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters. Trudy Instituta Matematiki i Mekhaniki UrO RAN 21(3), 100\u2013109 (2015). (in Russian)","journal-title":"Trudy Instituta Matematiki i Mekhaniki UrO RAN"},{"key":"5_CR7","volume-title":"Computers and Intractability. A Guide to the Theory of $$NP$$ -Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of \n                    \n                      \n                    \n                    $$NP$$\n                  -Completeness. W.H. Freeman and Company, San Francisco (1979)"},{"issue":"3","key":"5_CR8","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1134\/S1990478909030041","volume":"3","author":"EK Gimadi","year":"2009","unstructured":"Gimadi, E.K., Glazkov, Y.V., Rykov, I.A.: On two problems of choosing some subset of vectors with integer coordinates that has maximum norm of the sum of elements in euclidean space. J. Appl. Ind. Math. 3(3), 343\u2013352 (2009)","journal-title":"J. Appl. Ind. Math."},{"issue":"25","key":"5_CR9","first-page":"55","volume":"9","author":"EK Gimadi","year":"2006","unstructured":"Gimadi, E.K., Kel\u2019manov, A.V., Kel\u2019manova, M.A., Khamidullin, S.A.: Aposteriori finding a quasiperiodic fragment with given number of repetitions in a number sequence (in Russian). Sibirskii Zhurnal Industrial\u2019noi Matematiki 9(25), 55\u201374 (2006)","journal-title":"Sibirskii Zhurnal Industrial\u2019noi Matematiki"},{"issue":"1","key":"5_CR10","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1134\/S1054661808010057","volume":"18","author":"EK Gimadi","year":"2008","unstructured":"Gimadi, E.K., Kel\u2019manov, A.V., Kel\u2019manova, M.A., Khamidullin, S.A.: A posteriori detecting a quasiperiodic fragment in a numerical sequence. Pattern Recogn. Image Anal. 18(1), 30\u201342 (2008)","journal-title":"Pattern Recogn. Image Anal."},{"issue":"4","key":"5_CR11","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1134\/S1990478910010084","volume":"4","author":"EK Gimadi","year":"2010","unstructured":"Gimadi, E.K., Pyatkin, A.V., Rykov, I.A.: On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension. J. Appl. Ind. Math. 4(4), 48\u201353 (2010)","journal-title":"J. Appl. Ind. Math."},{"issue":"3","key":"5_CR12","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1134\/S1990478915030060","volume":"9","author":"EK Gimadi","year":"2015","unstructured":"Gimadi, E.K., Rykov, I.A.: A randomized algorithm for finding a subset of vectors. J. Appl. Ind. Math. 9(3), 351\u2013357 (2015)","journal-title":"J. Appl. Ind. Math."},{"key":"5_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21606-5","volume-title":"The Elements of Statistical Learning: Data Mining, Inference, and Prediction","author":"T Hastie","year":"2001","unstructured":"Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, New York (2001)"},{"issue":"S2","key":"5_CR14","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1134\/S0081543808060096","volume":"263","author":"AV Kel\u2019manov","year":"2008","unstructured":"Kel\u2019manov, A.V.: Off-line detection of a quasi-periodically recurring fragment in a numerical sequence. Proc. Steklov Inst. Math. 263(S2), 84\u201392 (2008)","journal-title":"Proc. Steklov Inst. Math."},{"issue":"11","key":"5_CR15","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1134\/S0965542510110163","volume":"50","author":"AV Kel\u2019manov","year":"2010","unstructured":"Kel\u2019manov, A.V.: On the complexity of some data analysis problems. Comput. Math. Math. Phys. 50(11), 1941\u20131947 (2010)","journal-title":"Comput. Math. Math. Phys."},{"issue":"11","key":"5_CR16","doi-asserted-by":"publisher","first-page":"1983","DOI":"10.1134\/S0965542511110108","volume":"51","author":"AV Kel\u2019manov","year":"2011","unstructured":"Kel\u2019manov, A.V.: On the complexity of some cluster analysis problems. Comput. Math. Math. Phys. 51(11), 1983\u20131988 (2011)","journal-title":"Comput. Math. Math. Phys."},{"key":"5_CR17","unstructured":"Kel\u2019manov, A.V., Khamidullin, S.A., Kel\u2019manova, M.A.: Joint finding and evaluation of a repeating fragment in noised number sequence with given number of quasiperiodic repetitions (in Russian). In: Book of Abstracts of the Russian Conference \u201cDiscret Analysis and Operations Research\u201d (DAOR-2004), p. 185. Sobolev Institute of Mathematics SB RAN, Novosibirsk (2004)"},{"issue":"4","key":"5_CR18","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1134\/S1990478913040066","volume":"7","author":"AV Kel\u2019manov","year":"2013","unstructured":"Kel\u2019manov, A.V., Khandeev, V.I.: A 2-approximation polynomial algorithm for a clustering problem. J. Appl. Ind. Math. 7(4), 515\u2013521 (2013)","journal-title":"J. Appl. Ind. Math."},{"issue":"2","key":"5_CR19","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1134\/S096554251502013X","volume":"55","author":"AV Kel\u2019manov","year":"2015","unstructured":"Kel\u2019manov, A.V., Khandeev, V.I.: A randomized algorithm for two-cluster partition of a set of vectors. Comput. Math. Math. Phys. 55(2), 330\u2013339 (2015)","journal-title":"Comput. Math. Math. Phys."},{"issue":"4","key":"5_CR20","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1134\/S1990478915040067","volume":"9","author":"AV Kel\u2019manov","year":"2015","unstructured":"Kel\u2019manov, A.V., Khandeev, V.I.: An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors. J. Appl. Ind. Math. 9(4), 497\u2013502 (2015)","journal-title":"J. Appl. Ind. Math."},{"issue":"2","key":"5_CR21","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1134\/S0965542516020111","volume":"56","author":"AV Kel\u2019manov","year":"2016","unstructured":"Kel\u2019manov, A.V., Khandeev, V.I.: Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem. Comput. Math. Math. Phys. 56(2), 334\u2013341 (2016)","journal-title":"Comput. Math. Math. Phys."},{"issue":"1","key":"5_CR22","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1134\/S1064562408040273","volume":"78","author":"AV Kel\u2019manov","year":"2008","unstructured":"Kel\u2019manov, A.V., Pyatkin, A.V.: On the complexity of a search for a subset of \u201csimilar\u201d vectors. Doklady Math. 78(1), 574\u2013575 (2008)","journal-title":"Doklady Math."},{"issue":"4","key":"5_CR23","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1134\/S1990478909040036","volume":"3","author":"AV Kel\u2019manov","year":"2009","unstructured":"Kel\u2019manov, A.V., Pyatkin, A.V.: On a version of the problem of choosing a vector subset. J. Appl. Ind. Math. 3(4), 447\u2013455 (2009)","journal-title":"J. Appl. Ind. Math."},{"issue":"11","key":"5_CR24","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1134\/S0965542509110128","volume":"49","author":"AV Kel\u2019manov","year":"2009","unstructured":"Kel\u2019manov, A.V., Pyatkin, A.V.: Complexity of certain problems of searching for subsets of vectors and cluster analysis. Comput. Math. Math. Phys. 49(11), 1966\u20131971 (2009)","journal-title":"Comput. Math. Math. Phys."},{"key":"5_CR25","unstructured":"Tarasenko, E.: On complexity of single-hub selection problem. In: Proceedings of 24-th Regional Conference of Students \u201cMolodezh tretjego tysacheletija\u201d, pp. 45\u201348. Omsk State University, Omsk (2010). (in Russian)"}],"container-title":["Communications in Computer and Information Science","Analysis of Images, Social Networks and Texts"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-52920-2_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T08:43:38Z","timestamp":1558514618000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-52920-2_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319529196","9783319529202"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-52920-2_5","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"17 February 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AIST","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Analysis of Images, Social Networks and Texts","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Yekaterinburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 April 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 April 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aist2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/aistconf.org\/2016\/en","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}