Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

The support of integer optimal solutions

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

[thumbnail of intergerbasicsupport-4siamopt.pdf]
Preview
PDF - Accepted Post-Print Version
Download (225kB) | Preview

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: 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: 06 Nov 2023 16:58
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 Edit Item

Downloads

Downloads per month over past year

View more statistics