A strongly polynomial algorithm for bimodular integer linear programming
From MaRDI portal
Publication:4978060
DOI10.1145/3055399.3055473zbMath1369.68350OpenAlexW2626905092MaRDI QIDQ4978060
S. Artmann, Rico Zenklusen, Robert Weismantel
Publication date: 17 August 2017
Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3055399.3055473
Related Items
Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles, The Integrality Number of an Integer Program, Notes on \(\{a,b,c\}\)-modular matrices, On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants, Enumerating Integer Points in Polytopes with Bounded Subdeterminants, On lattice point counting in \(\varDelta\)-modular polyhedra, On the maximal number of columns of a \(\varDelta \)-modular matrix, The computational complexity of dominating set problems for instances with bounded minors of constraint matrices, A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs, Integer programming in parameterized complexity: five miniatures, On Lattice Width of Lattice-Free Polyhedra and Height of Hilbert Bases, Advances on strictly \(\varDelta \)-modular IPs, New Bounds for the Integer Carathéodory Rank, On the Column Number and Forbidden Submatrices for \(\Delta\)-Modular Matrices, Complexity of optimizing over the integers, Unnamed Item, Nonnegative partial \(s\)-goodness for the equivalence of a 0-1 linear program to weighted linear programming, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), Faster Algorithms for Integer Programs with Block Structure, FPT-algorithms for some problems related to integer programming, A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices, Subdeterminants and Concave Integer Quadratic Programming, A new contraction technique with applications to congruency-constrained cuts, On the recognition of \(\{a,b,c\}\)-modular matrices, FPT-algorithm for computing the width of a simplex given by a convex hull, 2-Modular Matrices, Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations, An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem, The integrality number of an integer program, Extended formulations for stable set polytopes of graphs without two disjoint odd cycles
