EN|RU
English version: Journal of Applied and Industrial Mathematics, 2020, 14:1, 56-72 |
![]() |
Volume 27, No 1, 2020, P. 17-42 UDC 519.854
Keywords: quasiconvex function, convex function, conic function, quasiconvex polynomial, integral lattice, nonlinear integer programming, successive minima, reduced basis of a lattice. DOI: 10.33048/daio.2020.27.654 Dmitry V. Gribanov 1 Received April 2, 2019 References[1] A. Yu. Chirkov, Minimization of a quasiconvex function on 2-dimensional lattice, Vestn. Lobachevsky State Univ. Nizhny Novgorod, Ser. Model. Optim. Control 1, 227–238 (2003).[2] A. Ahmadi, A. Olshevsky, P. Parrilo, and J. Tsitsiklis, NP-hardness of deciding convexity of quadratic polynomials and related problems, Math. Program. 137 (1–2), 453–476 (2013). [3] D. Dadush, Integer programming, lattice algorithms, and deterministic volume estimation, Ph. D. Thesis (ProQuest LLC, Ann Arbor, MI; Georgia Institute of Technology, 2012). [4] D. Dadush, C. Peikert, and S. Vempala, Enumerative lattice algorithms in any norm via $M$-ellipsoid coverings, in Proc. 52nd Annual IEEE Symp. Foundations of Computer Science, Palm Springs, CA, USA, Oct. 23–25, 2011 (IEEE Comput. Soc., Washington, 2011), pp. 580–589. [5] L. Khachiyan and L. Porkolab, Integer optimization on convex semialgebraic sets, Discrete Comput. Geom. 23 (2), 207–224 (2000). [6] H. Lenstra, Integer programming with a fixed number of variables, Math. Oper. Res. 8 (4), 538–548 (1983). [7] J. A. de Loera, R. Hemmecke, M. Koppe, and R. Weismantel, Integer polynomial optimization in fixed dimension, Math. Oper. Res. 31 (1), 147–153 (2006). [8] S. Heinz, Complexity of integer quasiconvex polynomial optimization, J. Complexity 21 (4), 543–556 (2005). [9] S. Heinz, Quasiconvex functions can be approximated by quasiconvex polynomials, ESAIM Control Optim. Calc. Var. 14 (4), 795–801 (2008). [10] R. Hemmecke, S. Onn, and R. Weismantel, A polynomial oracle-time algorithm for convex integer minimization, Math. Program. 126 (1), 97–117 (2011). [11] R. Hildebrand and M. Köppe, A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity $2^{O(n log n)}$, Discrete Optim. 10 (1), 69–84 (2013). [12] T. Oertel, Integer convex minimization in low dimensions, Ph. D. Thesis (Eidgenössische Technische Hochschule, Zürich, 2014). [13] T. Oertel, C. Wagner, and R. Weismantel, Integer convex minimization by mixed integer linear optimization, Oper. Res. Lett. 42 (6), 424–428 (2014). [14] A. Basu and T. Oertel, Centerpoints: A link between optimization and convex geometry, SIAM J. Optim. 27 (2), 866–889 (2017). [15] A. Yu. Chirkov, D. V. Gribanov, D. S. Malyshev, P. M. Pardalos, S. I. Veselov, and A. Yu. Zolotykh, On the complexity of quasiconvex integer minimization problem, J. Global Optim. 73 (4), 761–788 (2018). [16] S. I. Veselov, D. V. Gribanov, N. Yu. Zolotykh, and A. Yu. Chirkov, Minimizing a symmetric quasiconvex function on a two-dimensional lattice, Diskretn. Anal. Issled. Oper. 25 (3), 23–35 (2018) [J. Appl. Ind. Math. 12 (3), 587–594 (2018)]. [17] D. Micciancio, Efficient reductions among lattice problems, in Proc. 19th Annual ACM-SIAM Symp. Discrete Algorithms, San Francisco, California, Jan. 20–22, 2008 (SIAM, Philadelphia, PA, 2008), pp. 84–93. [18] D. Micciancio and P. Voulgaris, A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations, SIAM J. Comput. 42 (3), 1364–1391 (2010). [19] D. Aggarwal, D. Dadush, O. Regev, and N. Stephens-Davidowitz, Solving the shortest vector problem in $2^n$ time via discrete Gaussian sampling, in Proc. 47th Annual ACM Symp. Theory of Computing, Portland, OR, USA, June 14–17, 2015 (ACM, New York, 2015), pp. 733–742. [20] D. Aggarwal, D. Dadush, and N. Stephens-Davidowitz, Solving the closest vector problem in $2^n$ time – the discrete Gaussian strikes again! in Proc. 56th Annual IEEE Symp. Foundations of Computer Science, Berkeley, CA, USA, Oct. 18–20, 2015, (IEEE Comput. Soc., Washington, 2011), pp. 563–582. [21] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics – A Foundation for Computer Science, (Addison-Wesley Prof., Reading, MA, 1994). [22] J. Cassels, An Introduction to the Geometry of Numbers (Springer, Berlin, 1997). [23] J. Edmonds, Systems of distinct representatives and linear algebra, J. Res. Natl. Bureau of Stand. B: Math. Math. Phys. 71 B (4), 241–245 (1967). [24] M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, in Algorithms and Combinatorics, Vol. 2, (Springer, Berlin, 1993). |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|