Integer programs with bounded subdeterminants and two nonzeros per row

Samuel Fiorini, Gwenael Joret, Stefan Weltge, Yelena Yuditsky

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

16 Scopus citations

Abstract

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k=0 (bipartite graphs) and for k=1. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching.

Original languageEnglish
Title of host publicationProceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
PublisherIEEE Computer Society
Pages13-24
Number of pages12
ISBN (Electronic)9781665420556
DOIs
StatePublished - 2022
Event62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States
Duration: 7 Feb 202210 Feb 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-February
ISSN (Print)0272-5428

Conference

Conference62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Country/TerritoryUnited States
CityVirtual, Online
Period7/02/2210/02/22

Keywords

  • integer programming
  • odd cycle packing number
  • stable set
  • subdeterminants

Fingerprint

Dive into the research topics of 'Integer programs with bounded subdeterminants and two nonzeros per row'. Together they form a unique fingerprint.

Cite this