Convex minization over \(\mathbb Z^2\). (English) Zbl 1207.90078
Summary: We present an algorithm for minimizing a convex function over all integer vectors in the plane. This problem generalizes both the nearest lattice vector problem and the integer programming problem in the plane.
References:
| [1] | Chaudhuri, K.; Kothari, A.; Pendavingh, R.; Swaminathan, R.; Tarjan, R.; Zhou, Y., Server allocation algorithms for tiered systems, Algorithmica, 48, 129-146 (2007) · Zbl 1124.68116 |
| [2] | Eisenbrand, F., Integer programming and algorithmic geometry of numbers, (Jünger, M.; Liebling, T.; Naddef, D.; Nemhauser, G.; Pulleyblank, W.; Reinelt, G.; Rinaldi, G.; Wolsey, L., 50 Years of Integer Programming 1958-2008 (2010), Springer-Verlag: Springer-Verlag Berlin), 505-556, From the early years to the state-of-the-art, Papers from the 12th Combinatorial Optimization Workshop (AUSSOIS 2008) held in Aussois, January 7-11, 2008 · Zbl 1187.90197 |
| [3] | Eisenbrand, F.; Laue, S., A linear algorithm for integer programming in the plane, Math. Program., 102, 249-259 (2005) · Zbl 1079.90581 |
| [4] | Gauss, C. F., Disquisitiones Arithmeticae (1986), Springer-Verlag: Springer-Verlag New York, Translated and with a preface by Arthur A. Clarke, Revised by William C. Waterhouse, Cornelius Greither and A.W. Grootendorst and with a preface by Waterhouse · Zbl 0585.10001 |
| [5] | Kaib, M.; Schnorr, C. P., The generalized Gauss reduction algorithm, J. Algorithms, 21, 565-578 (1996) · Zbl 0876.68049 |
| [6] | Micciancio, D.; Goldwasser, S., (Complexity of Lattice Problems. Complexity of Lattice Problems, The Kluwer International Series in Engineering and Computer Science, vol. 671 (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA), A cryptographic perspective · Zbl 1140.94010 |
| [7] | Vallée, B., Gauss’ algorithm revisited, J. Algorithms, 12, 556-572 (1991) · Zbl 0779.11065 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
