Advances on strictly -modular IPs

DOI10.1007/978-3-031-32726-1_28MaRDI QIDQ6086017zbMATH OpenOpenAlexFDO

Authors Martin Nägele, Christian Nöbel, Richard Santiago, Rico Zenklusen

Publication date 9 November 2023

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-32726-1_28

zbMATH Keywords

bounded subdeterminantscongruency constraints

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the Column Number and Forbidden Submatrices for -Modular Matrices
• Congruency-constrained TU problems beyond the bimodular case
• Polynomial Upper Bounds on the Number of Differing Columns of Δ-Modular Integer Programs
• A strongly polynomial algorithm for bimodular integer linear programming
• On integer programming with bounded determinants

Cites work

• A construction for binary matroids
• A new contraction technique with applications to congruency-constrained cuts
• A note on non-degenerate integer programs with small sub-determinants
• A strongly polynomial algorithm for bimodular integer linear programming
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• An FPTAS for the -modular multidimensional knapsack problem
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• Decomposition of regular matroids
• Geometric algorithms and combinatorial optimization.
• Geometric random edge
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• Improving proximity bounds using sparsity
• Integer program with bimodular matrix
• Minimizing submodular functions over families of sets
• Odd Minimum Cut-Sets and b-Matchings
• On -modular integer linear problems in the canonical form and equivalent problems
• On integer programming with bounded determinants
• On largest volume simplices and sub-determinants
• On linear systems with integral valued solutions
• On the maximal number of columns of a \(\varDelta \)-modular matrix
• On the number of distinct rows of a matrix with bounded subdeterminants
• On the recognition of \(\{a,b,c\}\)-modular matrices
• Polynomial Upper Bounds on the Number of Differing Columns of Δ-Modular Integer Programs
• Random pseudo-polynomial algorithms for exact matroid problems
• Randomized rounding for the largest simplex problem
• Regular matroids have polynomial extension complexity
• The Integrality Number of an Integer Program

Cited in

(12)

• On self-regular IPMs (with comments and rejoinder)
• On the Column Number and Forbidden Submatrices for -Modular Matrices
• On -modular integer linear problems in the canonical form and equivalent problems
• Congruency-constrained TU problems beyond the bimodular case
• On the exact matching problem in dense graphs
• Extended formulations for the integer hull of strictly -modular cographic polyhedral cones
• On the size of integer programs with bounded non-vanishing subdeterminants
• On the congruency-constrained matroid base
• On matrices over a polynomial ring with restricted subdeterminants
• Total matching and subdeterminants
• On the complexity of the odd-red bipartite perfect matching polytope
• Mathematical programming approaches for social welfare maximization

This page was built for publication: Advances on strictly \(\varDelta \)-modular IPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6086017)