Aliev, I.  ORCID: https://orcid.org/0000-0002-2206-9207, De Loera, J. A., Eisenbrand, F., Oertel, T. ORCID: https://orcid.org/0000-0001-5720-8978 and Weismantel, R.
2018.
The support of integer optimal solutions.
SIAM Journal on Optimization
28
(3)
, pp. 2152-2157.
10.1137/17M1162792
|
Preview |
PDF
- Accepted Post-Print Version
Download (225kB) | Preview |
Official URL: http://dx.doi.org/10.1137/17M1162792
Abstract
The support of a vector is the number of nonzero-components. We show that given an integral m×n matrix A, the integer linear optimization problem max{cTx:Ax=b,x≥0,x∈Zn} has an optimal solution whose support is bounded by 2mlog(2m−−√∥A∥∞), where ∥A∥∞ is the largest absolute value of an entry of A. Compared to previous bounds, the one presented here is independent on the objective function. We furthermore provide a nearly matching asymptotic lower bound on the support of optimal solutions.
| Item Type: | Article |
|---|---|
| Date Type: | Published Online |
| Status: | Published |
| Schools: | Schools > Mathematics |
| Publisher: | Society for Industrial and Applied Mathematics |
| ISSN: | 1052-6234 |
| Date of First Compliant Deposit: | 30 April 2018 |
| Date of Acceptance: | 5 April 2018 |
| Last Modified: | 05 Dec 2024 02:45 |
| URI: | https://orca.cardiff.ac.uk/id/eprint/111105 |
Citation Data
Cited 19 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
 |
Edit Item |
Altmetric
Altmetric