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

The support of integer optimal solutions

Aliev, Iskander, De Loera, Jesus, Friedrich, Eisenbrand, Oertel, Timm and Weismantel, Robert 2018. The support of integer optimal solutions. SIAM Journal on Optimization 28 (3) , pp. 2152-2157. 10.1137/17M1162792

[img]
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: Publication
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: 7 April 2018
Last Modified: 28 Apr 2019 12:37
URI: http://orca.cf.ac.uk/id/eprint/111105

Citation Data

Cited 1 time 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