The distributions of functions related to parametric integer optimization

Oertel, Timm ORCID: https://orcid.org/0000-0001-5720-8978, Paat, Joseph and Weismantel, Robert 2020. The distributions of functions related to parametric integer optimization. SIAM Journal on Applied Algebra and Geometry 4 (3) , pp. 422-440. 10.1137/19M1275954

Preview

PDF - Accepted Post-Print Version Download (374kB) | Preview

Abstract

We consider the asymptotic distribution of the integer program (IP) sparsity function, which measures the minimal support of optimal IP solutions, and the IP to linear program (LP) distance function, which measures the distance between optimal IP and LP solutions. We create a framework for studying the asymptotic distributions of general functions related to integer optimization. There has been a significant amount of research focused on the extreme values that these functions can attain. However, less is known about their typical values. Each of these functions is defined for a fixed constraint matrix and objective vector while the right-hand sides are treated as input. We show that the typical values of these functions are smaller than the known worst case bounds by providing a spectrum of probability-like results that govern their overall asymptotic distributions.Read More: https://epubs.siam.org/doi/10.1137/19M1275954

Item Type:	Article
Date Type:	Published Online
Status:	Published
Schools:	Mathematics
ISSN:	2470-6566
Date of First Compliant Deposit:	17 September 2020
Date of Acceptance:	22 July 2020
Last Modified:	21 Nov 2024 20:15
URI:	https://orca.cardiff.ac.uk/id/eprint/134904

Citation Data

Cited 7 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item