Polynomial Upper Bounds on the Number of Differing Columns of Δ-Modular Integer Programs

References

• [1] Aliev I, De Loera J, Oertel T, O’Neil C (2017) Sparse solutions of linear diophantine equations. SIAM J. Appl. Algebra Geometry 1(1):239–253.Crossref, Google Scholar
• [2] Anstee R (1990) Forbidden configurations, discrepancy and determinants. Eur. J. Combinatorics 11(1):15–19.Crossref, Google Scholar
• [3] Artmann S, Weismantel R, Zenklusen R (2017) A strongly polynomial algorithm for bimodular integer linear programming. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1206–1219.Google Scholar
• [4] Averkov G, Schymura M (2021) Personal communication.Google Scholar
• [5] Barvinok A (2002) A Course in Convexity, vol. 54 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [6] Cevallos A, Weltge S, Zenklusen R (2018) Lifting linear extension complexity bounds to the mixed-integer setting. Proc. 2018 Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 788–807.Google Scholar
• [7] Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming (Springer, Cham, Switzerland).Crossref, Google Scholar
• [8] Conforti M, Fiorini S, Huynh T, Weltge S (2020) Extended formulations for stable set polytopes of graphs without two disjoint odd cycles. Proc. 2020 Internat. Integer Programming Combinatorial Optim. (Springer, Cham, Switzerland), 104–116.Google Scholar
• [9] Conforti M, Fiorini S, Huynh T, Joret G, Weltge S (2020) The stable set problem in graphs with bounded genus and bounded odd cycle packing number. Proc. 2020 ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2896–2915.Google Scholar
• [10] Cook S (1971) The complexity of theorem-proving procedures. Proc. 1971 ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 151–158.Google Scholar
• [11] Cook W, Gerards A, Schrijver A, Tardos É (1986) Sensitivity theorems in integer linear programming. Math. Programming 34(3):251–264.Crossref, Google Scholar
• [12] De Loera J, Hemmecke R, Köppe M (2012) Algebraic and Geometric Ideas in the Theory of Discrete Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Google Scholar
• [13] Diaconis P, Graham R, Sturmfels B (1996) Primitive partition identities. Combinatorics 80:1–20.Google Scholar
• [14] Eisenbrand F, Weismantel R (2018) Proximity results and faster algorithms for integer programming using the Steinitz lemma. Proc. Twenty-Ninth Annual ACM-SIAM Sympos. Discrete Algorithms (Association for Computing Machinery, New York), 808–816.Google Scholar
• [15] Eisenbrand F, Hunkenschröder C, Klein K (2018) Faster algorithms for integer programs with block structure. Preprint, submitted February 17, https://arxiv.org/abs/1802.06289.Google Scholar
• [16] Geelen J, Nelson P, Walsh Z (2021) Excluding a line from C-representable matroids. Preprint, submitted January 28, https://arxiv.org/abs/2101.12000.Google Scholar
• [17] Glanzer C, Stallknecht I, Weismantel R (2021) On the recognition of {a,b,c}-modular matrices. Singh M, Williamson DP, eds. Integer Programming and Combinatorial Optimization (Springer, Cham, Switzerland), 238–251.Crossref, Google Scholar
• [18] Glanzer C, Weismantel R, Zenklusen R (2018) On the number of distinct rows of a matrix with bounded subdeterminants. SIAM J. Discrete Math. 32(3):1706–1720.Crossref, Google Scholar
• [19] Granot F, Skorin-Kapov J (1990) Some proximity and sensitivity results in quadratic integer programming. Math. Programming 47(1):259–268.Crossref, Google Scholar
• [20] Heller I (1957) On linear systems with integral valued solutions. Pacific J. Math. 7(3):1351–1364.Crossref, Google Scholar
• [21] Hochbaum DS, Shanthikumar JG (1990) Convex separable optimization is not much harder than linear optimization. J. ACM 37(4):843–862.Crossref, Google Scholar
• [22] Hoffman A, Kruskal J (1956) Integral boundary points of convex polyhedra. Linear Inequalities Related Systems 24:223–246.Google Scholar
• [23] Kung J (1990) Combinatorial geometries representable over GF(3) and GF(q). I. The number of points. Discrete Comput. Geometry 5(1):83–95.Crossref, Google Scholar
• [24] Kung J (1990) The long-line graph of a combinatorial geometry. II. Geometries representable over two fields of different characteristics. J. Combinatorial Theory Series B 50(1):41–53.Crossref, Google Scholar
• [25] Lee J (1989) Subspaces with well-scaled frames. Linear Algebra Appl. 115:21–56.Crossref, Google Scholar
• [26] Lee J, Paat J, Stallknecht I, Xu L (2020) Improving proximity bounds using sparsity. Proc. 2020 Internat. Sympos. Combinatorial Optim. (Springer, Cham, Switzerland), 115–127.Google Scholar
• [27] Lenstra H (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.Link, Google Scholar
• [28] Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization, Wiley Interscience Series in Discrete Mathematics and Optimization (Wiley, New York).Crossref, Google Scholar
• [29] OEIS Foundation Inc. (2018) The on-line encyclopedia of integer sequences. Accessed January 1, 2021, https://oeis.org/A085548.Google Scholar
• [30] Oertel T, Paat J, Weismantel R (2020) The distributions of functions related to parametric integer optimization. SIAM J. Appl. Algebra Geometry 4(3):422–440.Crossref, Google Scholar
• [31] Oxley JG (1992) Matroid Theory (Oxford University Press, Oxford, United Kingdom).Google Scholar
• [32] Oxley J, Walsh Z (2022) 2-modular matrices. SIAM J. Discrete Math. 36(2).Google Scholar
• [33] Paat J, Schlöter M, Weismantel R (2022) The integrality number of an integer program. Math. Programming 192(1):271–291.Crossref, Google Scholar
• [34] Paat J, Weismantel R, Weltge S (2018) Distances between optimal solutions of mixed-integer programs. Math. Programming 179(1):455–467.Crossref, Google Scholar
• [35] Schrijver A (1986) Theory of Linear and Integer Programming (John Wiley & Sons, Inc., New York).Google Scholar
• [36] Seymour P (1980) Decomposition of regular matroids. J. Combinatorial Theory Series B 28(3):305–359.Crossref, Google Scholar
• [37] Veselov S, Chirkov A (2009) Integer programming with bimodular matrix. Discrete Optim. 6(2):220–222.Crossref, Google Scholar
• [38] Werman M, Magagnosc D (1991) The relationship between integer and real solutions of constrained convex programming. Math. Programming 51(1):133–135.Crossref, Google Scholar