{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T12:00:02Z","timestamp":1775304002410,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,12,11]],"date-time":"2018-12-11T00:00:00Z","timestamp":1544486400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"crossref","award":["17-11-01336"],"award-info":[{"award-number":["17-11-01336"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s10898-018-0729-8","type":"journal-article","created":{"date-parts":[[2018,12,10]],"date-time":"2018-12-10T23:54:57Z","timestamp":1544486097000},"page":"761-788","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["On the complexity of quasiconvex integer minimization problem"],"prefix":"10.1007","volume":"73","author":[{"given":"A. Yu.","family":"Chirkov","sequence":"first","affiliation":[]},{"given":"D. V.","family":"Gribanov","sequence":"additional","affiliation":[]},{"given":"D. S.","family":"Malyshev","sequence":"additional","affiliation":[]},{"given":"P. M.","family":"Pardalos","sequence":"additional","affiliation":[]},{"given":"S. I.","family":"Veselov","sequence":"additional","affiliation":[]},{"given":"N. Yu.","family":"Zolotykh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,12,11]]},"reference":[{"issue":"1\u20132","key":"729_CR1","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s10107-011-0499-2","volume":"137","author":"A Ahmadi","year":"2013","unstructured":"Ahmadi, A., Olshevsky, A., Parrilo, P., Tsitsiklis, J.: NP-hardness of deciding convexity of quadratic polynomials and related problems. Math. Program. 137(1\u20132), 453\u2013476 (2013)","journal-title":"Math. Program."},{"key":"729_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 601\u2013610 (2001)","DOI":"10.1145\/380752.380857"},{"key":"729_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: Sampling short lattice vectors and the closest lattice vector problem. In: Proceedings of 17th IEEE Annual Conference on Computational Complexity, pp. 53\u201357 (2002)","DOI":"10.1109\/CCC.2002.1004339"},{"key":"729_CR4","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/BF01445125","volume":"296","author":"W Banaszczyk","year":"1993","unstructured":"Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296, 625\u2013635 (1993)","journal-title":"Math. Ann."},{"issue":"3","key":"729_CR5","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1287\/moor.24.3.728","volume":"24","author":"W Banaszczyk","year":"1999","unstructured":"Banaszczyk, W., Litvak, A., Pajor, A., Szarek, S.: The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces. Math. Oper. Res. 24(3), 728\u2013750 (1999)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"729_CR6","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1137\/16M1092908","volume":"27","author":"A Basu","year":"2017","unstructured":"Basu, A., Oertel, T.: Centerpoints: a link between optimization and convex geometry. SIAM J. Optim. 27(2), 866\u2013889 (2017)","journal-title":"SIAM J. Optim."},{"issue":"18","key":"729_CR7","doi-asserted-by":"publisher","first-page":"1648","DOI":"10.1016\/j.tcs.2008.12.045","volume":"410","author":"J Bl\u00f6mer","year":"2009","unstructured":"Bl\u00f6mer, J., Naewe, S.: Sampling methods for shortest vectors, closest vectors and successive minima. Theor. Comput. Sci. 410(18), 1648\u20131665 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"729_CR8","unstructured":"Bredereck, R., Faliszewski, P., Niedermeier, R., Skowron, P., Talmon, N: Mixed integer programming with convex\/concave constraints: fixed-parameter tractability and applications to multicovering and voting. CoRR, arXiv:1709.02850 (2017)"},{"key":"729_CR9","first-page":"227","volume":"1","author":"A Chirkov","year":"2003","unstructured":"Chirkov, A.: Minimization of a quasiconvex function on 2-dimensional lattice. Vestnik Lobachevsky State Univ Nizhni Novgorod Model. Opt. Control Ser. 1, 227\u2013238 (2003). (in Russian)","journal-title":"Vestnik Lobachevsky State Univ Nizhni Novgorod Model. Opt. Control Ser."},{"key":"729_CR10","unstructured":"Dadush, D.: Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation. ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.), Georgia Institute of Technology (2012)"},{"key":"729_CR11","doi-asserted-by":"crossref","unstructured":"Dadush, D., Peikert, C., Vempala, S.: Enumerative lattice algorithms in any norm via M-ellipsoid coverings. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 11), pp. 580\u2013589 (2011)","DOI":"10.1109\/FOCS.2011.31"},{"key":"729_CR12","unstructured":"Dinur, I., Kindler, G., Safra, S.: Approximating CVP to within almost-polynomial factors is NP-hard. In: 39th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, CA (1998)"},{"key":"729_CR13","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-540-39658-1_20","volume":"2832","author":"F Eisenbrand","year":"2003","unstructured":"Eisenbrand, F.: Fast integer programming in fixed dimension. ESA Lect. Notes Comput. Sci. 2832, 196\u2013207 (2003)","journal-title":"ESA Lect. Notes Comput. Sci."},{"key":"729_CR14","first-page":"1958","volume-title":"50 Years of Integer Programming","author":"F Eisenbrand","year":"2010","unstructured":"Eisenbrand, F.: Integer programming and algorithmic geometry of numbers. In: J\u00fcnger, M., Liebling, T., Naddef, D., Pulleyblank, W., Reinelt, G., Rinaldi, G., Wolsey, L. (eds.) 50 Years of Integer Programming, pp. 1958\u20132008. Springer, Berlin (2010)"},{"key":"729_CR15","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., H\u00e4hnle, N., Niemeier, M.: Covering cubes and the closest vector problem. In: Proceedings of 27th Annual Symposium on Computational Geometry, pp. 417\u2013423 (2011)","DOI":"10.1145\/1998196.1998264"},{"key":"729_CR16","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-12868-9_103","volume":"162","author":"U Fincke","year":"1983","unstructured":"Fincke, U., Pohst, M.: A procedure for determining algebraic integers of given norm. Lect. Notes Comput. Sci 162, 194\u2013202 (1983)","journal-title":"Lect. Notes Comput. Sci"},{"issue":"170","key":"729_CR17","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1090\/S0025-5718-1985-0777278-8","volume":"44","author":"U Fincke","year":"1985","unstructured":"Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44(170), 463\u2013471 (1985)","journal-title":"Math. Comput."},{"issue":"1","key":"729_CR18","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, E.: An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987)","journal-title":"Combinatorica"},{"key":"729_CR19","unstructured":"Gaven\u010diak, T., Knop, D., Kouteck\u00fd, M.: Applying Convex Integer Programming: Sum Multicoloring and Bounded Neighborhood Diversity. CoRR, arXiv:1711.02032 (2017)"},{"key":"729_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"key":"729_CR21","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-642-20901-7_10","volume":"6639","author":"G Hanrot","year":"2011","unstructured":"Hanrot, G., Pujol, X., Stehle, D.: Algorithms for the shortest and closest lattice vector problems. Lect. Notes Comput. Sci. 6639, 159\u2013190 (2011)","journal-title":"Lect. Notes Comput. Sci."},{"issue":"4","key":"729_CR22","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/j.jco.2005.04.004","volume":"21","author":"S Heinz","year":"2005","unstructured":"Heinz, S.: Complexity of integer quasiconvex polynomial optimization. J. Complex. 21(4), 543\u2013556 (2005)","journal-title":"J. Complex."},{"issue":"4","key":"729_CR23","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1051\/cocv:2008010","volume":"14","author":"S Heinz","year":"2008","unstructured":"Heinz, S.: Quasiconvex functions can be approximated by quasiconvex polynomials. ESAIM Control Optim. Calc. Var. 14(4), 795\u2013801 (2008)","journal-title":"ESAIM Control Optim. Calc. Var."},{"issue":"1","key":"729_CR24","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.disopt.2012.11.003","volume":"10","author":"R Hildebrand","year":"2013","unstructured":"Hildebrand, R., K\u00f6ppe, M.: A new lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity $$2^{O(n \\log n)}$$ 2 O ( n log n ) . Discrete Optim. 10(1), 69\u201384 (2013)","journal-title":"Discrete Optim."},{"key":"729_CR25","doi-asserted-by":"crossref","unstructured":"Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of 15th Annual ACM Symposium on Theory of Computing, pp. 99\u2013108 (1983)","DOI":"10.1145\/800061.808749"},{"issue":"3","key":"729_CR26","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"729_CR27","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/PL00009496","volume":"23","author":"L Khachiyan","year":"2000","unstructured":"Khachiyan, L., Porkolab, L.: Integer optimization on convex semialgebraic sets. Discrete Comput. Geom. 23(2), 207\u2013224 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"729_CR28","first-page":"113","volume":"12","author":"A Khinchin","year":"1948","unstructured":"Khinchin, A.: A quantitative formulation of Kronecker\u2019s theory of approximation. Izvestiya Akademii Nauk SSR Seriya Matematika 12, 113\u2013122 (1948). (in Russian)","journal-title":"Izvestiya Akademii Nauk SSR Seriya Matematika"},{"key":"729_CR29","doi-asserted-by":"crossref","unstructured":"K\u00f6ppe, M.: On the complexity of nonlinear mixed-integer optimization. In: Lee, J., Leyffer, S. (eds) Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its Applications 154. Springer, New York (2012)","DOI":"10.1007\/978-1-4614-1927-3_19"},{"issue":"4","key":"729_CR30","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H Lenstra","year":"1983","unstructured":"Lenstra, H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"729_CR31","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A Lenstra","year":"1982","unstructured":"Lenstra, A., Lenstra, H., Lovasz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515\u2013534 (1982)","journal-title":"Math. Ann."},{"issue":"6","key":"729_CR32","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1137\/S0097539700373039","volume":"30","author":"D Micciancio","year":"1998","unstructured":"Micciancio, D.: The shortest vector problem is NP-hard to approximate to within some constant. SIAM J. Comput. 30(6), 2008\u20132035 (1998)","journal-title":"SIAM J. Comput."},{"key":"729_CR33","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: STOC, pp. 351\u2013358 (2010)","DOI":"10.1145\/1806689.1806739"},{"key":"729_CR34","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"A Nemirovsky","year":"1983","unstructured":"Nemirovsky, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)"},{"key":"729_CR35","unstructured":"Oertel, T.: Integer Convex Minimization in Low Dimensions. Thes. doct. phylosophy, Eidgen\u00f6ssische Technische Hochschule, Z\u00fcrich (2014)"},{"key":"729_CR36","unstructured":"Oertel, T., Wagner, C., Weismantel, R.: Convex Integer Minimization in Fixed Dimension. https:\/\/arxiv.org\/pdf\/1203.4175.pdft (2012)"},{"issue":"6\u20137","key":"729_CR37","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.orl.2014.07.005","volume":"42","author":"T Oertel","year":"2014","unstructured":"Oertel, T., Wagner, C., Weismantel, R.: Integer convex minimization by mixed integer linear optimization. Oper. Res. Lett. 42(6\u20137), 424\u2013428 (2014)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"729_CR38","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1023\/A:1009842406728","volume":"4","author":"M Rudelson","year":"2000","unstructured":"Rudelson, M.: Distances between non-symmetric convex bodies and the $$M M^*$$ M M \u2217 -estimate. Positivity 4(2), 161\u2013178 (2000)","journal-title":"Positivity"},{"key":"729_CR39","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1998)"},{"key":"729_CR40","doi-asserted-by":"publisher","unstructured":"Veselov, S., Gribanov, D., Zolotykh, N., Chirkov, A.: Minimization of symmetric quasiconvex function on 2-dimensional lattice. Discrete Anal. Oper. Res. (2018). https:\/\/doi.org\/10.17377\/daio.2018.25.585 . (in Russian)","DOI":"10.17377\/daio.2018.25.585"},{"key":"729_CR41","unstructured":"Yudin, D., Nemirovskii, A.: Information complexity and efficient methods for the solution of convex extremal problems. Ekonomika i Matematicheskie Metody 12, 357\u2013369 [Translated in Matekon 13 (1977) 25\u201345] (1976). (in Russian)"},{"issue":"2","key":"729_CR42","first-page":"3","volume":"13","author":"D Yudin","year":"1976","unstructured":"Yudin, D., Nemirovski, A.: Evaluation of the information complexity of mathematical programming problems. Ekonomika i Matematicheskie Metody 13(2), 3\u201345 (1976). (in Russian)","journal-title":"Ekonomika i Matematicheskie Metody"},{"key":"729_CR43","first-page":"93","volume":"5","author":"N Zolotykh","year":"2012","unstructured":"Zolotykh, N., Chirkov, A.: Lower bound of the quasiconvex minimization problem on an integral lattice. Vestnik of Lobachevsky State University of Nizhni Novgorod Model. Opt. Control 5, 93\u201396 (2012). (in Russian)","journal-title":"Vestnik of Lobachevsky State University of Nizhni Novgorod Model. Opt. Control"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-018-0729-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-018-0729-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-018-0729-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T11:09:09Z","timestamp":1775300949000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-018-0729-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,11]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["729"],"URL":"https:\/\/doi.org\/10.1007\/s10898-018-0729-8","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,11]]},"assertion":[{"value":"2 August 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}