Congruency-Constrained TU Problems Beyond the Bimodular Case

References

• [1] Aprile M, Fiorini S (2021) Regular matroids have polynomial extension complexity. Math. Oper. Res. 47(1):540–559.Link, Google Scholar
• [2] Artmann S (2020) Optimization of bimodular integer programs and feasibility for three-modular base block IPs. PhD thesis, ETH Zurich. http://dx.doi.org/10.3929/ethz-b-000420070.Google Scholar
• [3] Artmann S, Weismantel R, Zenklusen R (2017) A strongly polynomial algorithm for bimodular integer linear programming. Proc. 49th Annual ACM SIGACT Symposium on Theory of Computing (Association for Computing Machinery, New York), 1206–1219.Google Scholar
• [4] Artmann S, Eisenbrand F, Glanzer C, Oertel T, Vempala S, Weismantel R (2016) A note on non-degenerate integer programs with small sub-determinants. Oper. Res. Lett. 44(5):635–639.Crossref, Google Scholar
• [5] Barahona F, Conforti M (1987) A construction for binary matroids. Discrete Math. 66(3):213–218.Crossref, Google Scholar
• [6] Bock AA, Faenza Y, Moldenhauer C, Ruiz-Vargas AJ (2014) Solving the stable set problem in terms of the odd cycle packing number. Raman V, Suresh SP, eds. Proc. 34th IARCS Annual Conf. Foundations Software Tech. Theoretical Comput. Sci. (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 187–198.Google Scholar
• [7] Bonifas N, Di Summa M, Eisenbrand F, Haehnle N, Niemeier M (2014) On sub-determinants and the diameter of polyhedra. Discrete Computat. Geometry 52(1):102–115.Crossref, Google Scholar
• [8] Camerini PM, Galbiati G, Maffioli F (1992) Random pseudo-polynomial algorithms for exact matroid problems. J. Algorithms 13(2):258–273.Crossref, Google Scholar
• [9] Conforti M, Fiorini S, Huynh T, Weltge S (2022) Extended formulations for stable set polytopes of graphs without two disjoint odd cycles. Math. Programming 192(1–2):547–566.Crossref, Google Scholar
• [10] 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. 31st ACM-SIAM Sympos. Discrete Algorithms (Association for Computing Machinery, New York), 2896–2915.Google Scholar
• [11] Di Summa M, Eisenbrand F, Faenza Y, Moldenhauer C (2015) On largest volume simplices and sub-determinants. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (Association for Computing Machinery, New York), 315–323.Google Scholar
• [12] Dinitz M, Kortsarz G (2014) Matroid secretary for regular and decomposable matroids. SIAM J. Comput. 43(5):1807–1830.Crossref, Google Scholar
• [13] Eisenbrand F, Vempala S (2017) Geometric random edge. Math. Programming 164(1):325–339.Crossref, Google Scholar
• [14] Fiorini S, Joret G, Weltge S, Yuditsky Y (2022) Integer programs with bounded subdeterminants and two nonzeros per row. Proc. 62nd Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 13–24.Google Scholar
• [15] Glanzer C, Stallknecht I, Weismantel R (2021) On the recognition of {a, b, c}-modular matrices. Proc. 22nd Internat. Conf. Integer Programming Combin. Optim. (Springer, New York), 238–251.Google Scholar
• [16] Goemans MX, Ramakrishnan VS (1995) Minimizing submodular functions over families of sets. Combinatorica 15(4):499–513.Crossref, Google Scholar
• [17] Grossman JW, Kulkarni DM, Schochetman IE (1995) On the minors of an incidence matrix and its Smith normal form. Linear Algebra Appl. 218:213–224.Crossref, Google Scholar
• [18] Grötschel M, Lovász L, Schrijver A (1984) Corrigendum to our paper “The ellipsoid method and its consequences in combinatorial optimization.” Combinatorica 4(4):291–295.Crossref, Google Scholar
• [19] Grötschel M, Lovász L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2 (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• [20] Lee J, Paat J, Stallknecht I, Xu L (2020) Improving proximity bounds using sparsity. Baïou M, Gendron B, Günlük O, Mahjoub AR, eds. Proc. Sixth Internat. Sympos. Combin. Optim., vol. 12176 (Springer, Cham, Switzerland), 115–127.Google Scholar
• [21] Lee J, Paat J, Stallknecht I, Xu L (2022) Polynomial upper bounds on the number of differing columns of Δ-modular integer programs. Preprint, submitted November 16, https://arxiv.org/abs/2105.08160.Google Scholar
• [22] Lenstra HW (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.Link, Google Scholar
• [23] Nägele M, Zenklusen R (2020) A new contraction technique with applications to congruency-constrained cuts. Math. Programming 183:455–481.Crossref, Google Scholar
• [24] Nägele M, Santiago R, Zenklusen R (2022) Congruency-constrained TU problems beyond the bimodular case. Naor (Seffi) J, Buchbinder N, eds. Proc. 33rd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2743–2790.Google Scholar
• [25] Nägele M, Sudakov B, Zenklusen R (2019) Submodular minimization under congruency constraints. Combinatorica 39(6):1351–1386.Crossref, Google Scholar
• [26] Nikolov A (2015) Randomized rounding for the largest simplex problem. Proc. 47th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 861–870.Google Scholar
• [27] Paat J, Schlöter M, Weismantel R (2022) The integrality number of an integer program. Math. Programming 192:271–291.Crossref, Google Scholar
• [28] Padberg MW, Rao MR (1982) Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7(1):67–80.Link, Google Scholar
• [29] Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar
• [30] Seymour PD (1980) Decomposition of regular matroids. J. Combin. Theory Ser. B 28(3):305–359.Crossref, Google Scholar
• [31] Tardos É (1986) A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34(2):250–256.Link, Google Scholar
• [32] Veselov SI, Chirkov AJ (2009) Integer program with bimodular matrix. Discrete Optim. 6(2):220–222.Crossref, Google Scholar