IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v48y2023i4p2267-2286.html
   My bibliography  Save this article

Polynomial Upper Bounds on the Number of Differing Columns of Δ-Modular Integer Programs

Author

Listed:
  • Jon Lee

    (Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109)

  • Joseph Paat

    (Sauder School of Business, University of British Columbia, Vancouver, British Columbia V6T 1Z2, Canada)

  • Ingo Stallknecht

    (Department of Mathematics, Eidgenossische Technische Hochschule Zurich, 8092 Zurich, Switzerland)

  • Luze Xu

    (Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109)

Abstract

We study integer-valued matrices with bounded determinants. Such matrices appear in the theory of integer programs (IPs) with bounded determinants. For example, an IP can be solved in strongly polynomial time if the constraint matrix is bimodular: that is, the determinants are bounded in absolute value by two. Determinants are also used to bound the ℓ 1 distance between IP solutions and solutions of its linear relaxation. One of the first to quantify the complexity of IPs with bounded determinants was Heller, who identified the maximum number of differing columns in a totally unimodular matrix. Each extension of Heller’s bound to general determinants has been superpolynomial in the determinants or the number of equations. We provide the first column bound that is polynomial in both values. For integer programs with box constraints, our result gives the first ℓ 1 distance bound that is polynomial in the determinants and the number of equations. Our result can also be used to derive a bound on the height of Graver basis elements that is polynomial in the determinants and the number of equations. Furthermore, we show a tight bound on the number of differing columns in a bimodular matrix; this is the first tight bound since Heller. Our analysis reveals combinatorial properties of bimodular IPs that may be of independent interest.

Suggested Citation

  • Jon Lee & Joseph Paat & Ingo Stallknecht & Luze Xu, 2023. "Polynomial Upper Bounds on the Number of Differing Columns of Δ-Modular Integer Programs," Mathematics of Operations Research, INFORMS, vol. 48(4), pages 2267-2286, November.
    • Handle: RePEc:inm:ormoor:v:48:y:2023:i:4:p:2267-2286
    DOI: 10.1287/moor.2022.1339
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.1339
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.1339?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:48:y:2023:i:4:p:2267-2286. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.