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

The distributions of functions related to parametric integer optimization

Oertel, Timm, 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

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


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:

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: 19 Jan 2021 18:51

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics