Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, Γ‰cole polytechnique fΓ©dΓ©rale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Books and Book parts
  4. A parameterized linear formulation of the integer hull
 
book part or chapter

A parameterized linear formulation of the integer hull

Eisenbrand, Friedrich  
β€’
Rothvoss, Thomas
January 2026
Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Let 𝐴 βˆˆβ„€π‘šΓ—π‘› be an integer matrix with entries bounded by Ξ” in absolute value. Cook et al. (1986) have shown that there exists a universal matrix 𝐡 βˆˆβ„€π‘šβ€²Γ—π‘› with the following property: For each 𝑏 βˆˆβ„€π‘š, there exists a 𝑑 βˆˆβ„€π‘šβ€² such that the integer hull of the polyhedron 𝑃 ={π‘₯ βˆˆβ„π‘› :𝐴⁒π‘₯ ≀𝑏} is described by 𝑃𝐼 ={π‘₯ βˆˆβ„π‘› :𝐡⁒π‘₯ ≀𝑑}. Our main result is that 𝑑 is an affine function of 𝑏 as long as 𝑏 is from a fixed equivalence class of the lattice 𝐷 β‹…β„€π‘š. Here 𝐷 βˆˆβ„• is a number that depends on 𝑛 and Ξ” only. Furthermore, 𝐷 as well as the matrix 𝐡 can be computed in time depending on 𝑛 and Ξ” only. An application of this result is the solution of an open problem posed by Cslovjecsek et al. (SODA 2024) concerning the complexity of 2-stage-stochastic integer programming problems. The main tool of our proof is the classical theory of ChvΓ‘tal-Gomory cutting planes and the elementary closure of rational polyhedra.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

2501.02347v3-1.pdf

Type

Main Document

Version

Submitted version (Preprint)

Access type

openaccess

License Condition

N/A

Size

609.72 KB

Format

Adobe PDF

Checksum (MD5)

c82b4e149fe776ac4177bb292af03717

Logo EPFL, Γ‰cole polytechnique fΓ©dΓ©rale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. Β© EPFL, tous droits rΓ©servΓ©s