The support of integer optimal solutions
Aliev I, De Loera JA, Eisenbrand F, Oertel T, Weismantel R (2018)
Publication Type: Journal article
Publication year: 2018
Journal
Book Volume: 28
Pages Range: 2152-2157
Journal Issue: 3
DOI: 10.1137/17M1162792
Abstract
The support of a vector is the number of nonzero components. We show that given anintegral m×n matrix A, the integer linear optimization problem maxfcT x: Ax = b; x = 0; x 2 Znghas an optimal solution whose support is bounded by 2m log(2pmkAk1), where kAk1 is the largestabsolute value of an entry of A. Compared to previous bounds, the one presented here is independentof the objective function. We furthermore provide a nearly matching asymptotic lower bound on thesupport of optimal solutions.
Authors with CRIS profile
Additional Organisation(s)
Involved external institutions
Cardiff University
United Kingdom (GB)
University of California Davis (UCDAVIS)
United States (USA) (US)
École Polytechnique Fédérale de Lausanne (EPFL)
Switzerland (CH)
Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich
Switzerland (CH)
United Kingdom (GB)
University of California Davis (UCDAVIS)
United States (USA) (US)
École Polytechnique Fédérale de Lausanne (EPFL)
Switzerland (CH)
Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich
Switzerland (CH)
How to cite
APA:
Aliev, I., De Loera, J.A., Eisenbrand, F., Oertel, T., & Weismantel, R. (2018). The support of integer optimal solutions. SIAM Journal on Optimization, 28(3), 2152-2157. https://dx.doi.org/10.1137/17M1162792
MLA:
Aliev, I., et al. "The support of integer optimal solutions." SIAM Journal on Optimization 28.3 (2018): 2152-2157.
BibTeX: Download