A note on non-degenerate integer programs with small sub-determinants
Artmann S, Eisenbrand F, Glanzer C, Oertel T, Vempala S, Weismantel R (2016)
Publication Type: Journal article
Publication year: 2016
Journal
Book Volume: 44
Pages Range: 635-639
Journal Issue: 5
DOI: 10.1016/j.orl.2016.07.004
Abstract
The intention of this note is two-fold. First, we study integer optimization problems in standard form defined by A∈Zm×n and find an algorithm to solve such problems in polynomial-time provided that both the largest absolute value of an entry in A and m are constant. Then, this is applied to solve integer programs in inequality form in polynomial-time, where the absolute values of all maximal sub-determinants of A lie between 1 and a constant.
Authors with CRIS profile
Additional Organisation(s)
Involved external institutions
Georgia Institute of Technology
United States (USA) (US)
Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich
Switzerland (CH)
Cardiff University
United Kingdom (GB)
École Polytechnique Fédérale de Lausanne (EPFL)
Switzerland (CH)
United States (USA) (US)
Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich
Switzerland (CH)
Cardiff University
United Kingdom (GB)
École Polytechnique Fédérale de Lausanne (EPFL)
Switzerland (CH)
How to cite
APA:
Artmann, S., Eisenbrand, F., Glanzer, C., Oertel, T., Vempala, S., & Weismantel, R. (2016). A note on non-degenerate integer programs with small sub-determinants. Operations Research Letters, 44(5), 635-639. https://dx.doi.org/10.1016/j.orl.2016.07.004
MLA:
Artmann, S., et al. "A note on non-degenerate integer programs with small sub-determinants." Operations Research Letters 44.5 (2016): 635-639.
BibTeX: Download