Oertel T, Paat J, Weismantel R (2020)
Publication Type: Journal article
Publication year: 2020
Book Volume: 4
Pages Range: 422-440
Journal Issue: 3
DOI: 10.1137/19M1275954
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.
APA:
Oertel, T., Paat, J., & Weismantel, R. (2020). The distributions of functions related to parametric integer optimization. SIAM Journal on Applied Algebra and Geometry, 4(3), 422-440. https://doi.org/10.1137/19M1275954
MLA:
Oertel, Timm, Joseph Paat, and Robert Weismantel. "The distributions of functions related to parametric integer optimization." SIAM Journal on Applied Algebra and Geometry 4.3 (2020): 422-440.
BibTeX: Download