Loading...
research article
The Support Of Integer Optimal Solutions
January 1, 2018
The support of a vector is the number of nonzero components. We show that given an integral mxn matrix A, the integer linear optimization problem max {c(T) x : Ax = b, x >= 0, x is an element of Z(n)} has an optimal solution whose support is bounded by 2m log(2 root m parallel to Lambda parallel to(infinity)), where parallel to Lambda parallel to(infinity) is the largest absolute value of an entry of A. Compared to previous bounds, the one presented here is independent of the objective function. We furthermore provide a nearly matching asymptotic lower bound on the support of optimal solutions.
Type
research article
Web of Science ID
WOS:000445767000010
Authors
Publication date
2018-01-01
Publisher
Published in
Volume
28
Issue
3
Start page
2152
End page
2157
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
December 13, 2018
Use this identifier to reference this record