Proximity and Flatness Bounds for Linear Integer Optimization

References

• [1] Aliev I, Henk M, Oertel T (2020) Distances to lattice points in knapsack polyhedra. Math. Programming 182:175–198.Crossref, Google Scholar
• [2] Aliev I, Celaya M, Henk M, Williams A (2021) Distance-sparsity transference for vertices of corner polyhedra. SIAM J. Optim. 31:200–216.Crossref, Google Scholar
• [3] Celaya M, Kuhlmann S, Paat J, Weismantel R (2022) Improving the Cook et al. proximity bound given integral valued constraints. Aardal K, Sanità L, eds. Integer Programming and Combinatorial Optimization IPCO 2022, Lecture Notes in Computer Science, vol. 13265 (Springer International Publishing, Cham, Switzerland), 84–97.Crossref, Google Scholar
• [4] Cook W, Gerards A, Schrijver A, Tardos E (1986) Sensitivity theorems in integer linear programming. Math. Programming 34:251–264.Crossref, Google Scholar
• [5] Del Pia A, Ma M (2021) Proximity in concave integer quadratic programming. Math. Programming 194:871–900.Google Scholar
• [6] Eisenbrand F, Weismantel R (2020) Proximity results and faster algorithms for integer programming using the Steinitz Lemma. ACM Trans. Algorithms 16:1–14.Crossref, Google Scholar
• [7] Fischetti M, Glover F, Lodi A (2005) The feasibility pump. Math. Programming 104:91–104.Crossref, Google Scholar
• [8] Florian A (1996) On the area sum of a convex set and its polar reciprocal. Mathematica Pannonica 7(2):171–176.Google Scholar
• [9] Fortier JM (2020) Self-polar planar polytopes: When finding the polar is rotating by pi. Master’s thesis, Concordia University, Montreal.Google Scholar
• [10] Granot F, Skorin-Kapov J (1990) Some proximity and sensitivity results in quadratic integer programming. Math. Programming 47:259–268.Crossref, Google Scholar
• [11] Gribanov D, Veselov S (2016) On integer programming with bounded determinants. Optim. Lett. 10:1169–1177.Crossref, Google Scholar
• [12] Gruber P (2007) Convex and Discrete Geometry (Springer-Verlag, Berlin).Google Scholar
• [13] Henk M, Kuhlmann S, Weismantel R (2022) On lattice width of lattice-free polyhedra and height of Hilbert bases. SIAM J. Discrete Math. 36(3):1918–1942.Crossref, Google Scholar
• [14] Hochbaum DS, Shanthikumar JG (1990) Convex separable optimization is not much harder than linear optimization. J. ACM 37:843–862.Crossref, Google Scholar
• [15] Jansen K, Rohwedder L (2019) On integer programming and convolution. Blum A, ed. 10th Innovations Theoret. Comput. Sci., vol. 43 (Dagstuhl Publishing, Germany), 1–17.Google Scholar
• [16] Jensen A (2021) Self-polar polytopes. Cunningham G, Mixer M, Schulte E, eds. Contemporary Mathematics: Polytopes and Discrete Geometry (American Mathematical Society, Providence, RI), 101–124.Crossref, Google Scholar
• [17] Jiang H, Basu A (2022) Enumerating integer points in polytopes with bounded subdeterminants. SIAM J. Discrete Math. 36(1):449–460.Crossref, Google Scholar
• [18] Khinchine A (1948) A quantitative formulation of Kronecker’s theory of approximation. Izv. Acad. Nauk SSSR 12:113–122.Google Scholar
• [19] Lee J, Paat J, Stallknecht I, Xu L (2020) Improving proximity bounds using sparsity. Proc. 2020 Internat. Sympos. Combinatorial Optim., 115–127.Google Scholar
• [20] Lee J, Paat J, Stallknecht I, Xu L (2021) Polynomial upper bounds on the number of differing columns of Δ-modular integer programs. Math. Oper. Res. 48:2267–2286.Google Scholar
• [21] Lenstra H (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.Link, Google Scholar
• [22] Mahler K (1939) Ein übertragungsprinzip für konvexe Körper (in German). Časopis Pešt. Mat. Fyz. 68:93–102.Google Scholar
• [23] Nägele M, Santiago R, Zenklusen R (2022) Congruency-constrained TU problems beyond the bimodular case. Proc. SODA 2022 (Society for Industrial and Applied Mathematics, Philadelphia).Google Scholar
• [24] Oertel T, Paat J, Weismantel R (2020) The distributions of functions related to parametric integer optimization. SIAM J. Appl. Algebra Geometry 4:422–440.Crossref, Google Scholar
• [25] Paat J, Weismantel R, Weltge S (2020) Distances between optimal solutions of mixed-integer programs. Math. Programming 179:455–468.Crossref, Google Scholar
• [26] Rudelson M (2000) Distances between nonsymmetric convex bodies and the MM*-estimate. Positivity 4(2):161–178.Crossref, Google Scholar
• [27] Santos F (2012) A counterexample to the Hirsch Conjecture. Ann. Math. 176:383–412.Crossref, Google Scholar
• [28] Schrijver A (1986) Theory of Linear and Integer Programming (John Wiley & Sons, Inc., New York).Google Scholar
• [29] Sturmfels B (1996) Gröbner Bases and Convex Polytopes, vol. 8, University Lecture Series (American Mathematical Society, Providence, RI).Google Scholar
• [30] Toth C, O’Rourke J, Goodman J (2017) Handbook of Discrete and Computational Geometry, 3rd ed. (Chapman and Hall/CRC, Boca Raton, FL).Google Scholar
• [31] Veselov S, Chirkov A (2009) Integer programming with bimodular matrix. Discrete Optim. 6:220–222.Crossref, Google Scholar
• [32] Werman M, Magagnosc D (1991) The relationship between integer and real solutions of constrained convex programming. Math. Programming 51:133–135.Crossref, Google Scholar
• [33] Xu L, Lee J (2019) On proximity for k-regular mixed-integer linear optimization. Proc. WCGO 2019 (Springer, Berlin, Germany), 438–447.Google Scholar