Integer programs with bounded subdeterminants and two nonzeros per row

DOI10.1145/3695985MaRDI QIDQ6854562zbMATH OpenFDO

Authors Samuel Fiorini, Gwenaël Joret, Stefan Weltge, Yelena Yuditsky

Publication date 24 February 2026

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3695985

zbMATH Keywords

graph minorsstable set problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Integer programming (90C10) Graph minors (05C83)

Cites work

• scientific article; zbMATH DE number 3812514 (Why is no real title available?)
• scientific article; zbMATH DE number 16301 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 863479 (Why is no real title available?)
• scientific article; zbMATH DE number 7559087 (Why is no real title available?)
• scientific article; zbMATH DE number 6297711 (Why is no real title available?)
• scientific article; zbMATH DE number 6297714 (Why is no real title available?)
• scientific article; zbMATH DE number 7788439 (Why is no real title available?)
• scientific article; zbMATH DE number 7788500 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A strongly polynomial algorithm for bimodular integer linear programming
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
• Face-width of embedded graphs
• Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs
• Geometric random edge
• Graph minors. XVI: Excluding a non-planar graph
• Graphs on surfaces
• Integer Programming with a Fixed Number of Variables
• Integer program with bimodular matrix
• Mangoes and blueberries
• Minkowski's Convex Body Theorem and Integer Programming
• Near-linear time algorithm for n-fold ILPs via color coding
• Odd cycle packing
• On sub-determinants and the diameter of polyhedra
• On the complexity of integer programming
• On the excluded minor structure theorem for graphs of large tree-width
• On the minors of an incidence matrix and Smith normal form
• On the odd-minor variant of Hadwiger's conjecture
• Polyhedral results on the stable set problem in graphs containing even or odd pairs
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Properties of vertex packing and independence system polyhedra
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• Sensitivity theorems in integer linear programming
• Solving the stable set problem in terms of the odd cycle packing number
• The Integrality Number of an Integer Program
• The stable set problem in graphs with bounded genus and bounded odd cycle packing number
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Vertex packings: Structural properties and algorithms
• \(n\)-fold integer programming in cubic time

Cited in

(1)

• Totally -modular IPs with two non-zeros in most rows

This page was built for publication: Integer programs with bounded subdeterminants and two nonzeros per row

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