Oertel T, Paat J, Weismantel R (2019)
Publication Type: Conference contribution
Publication year: 2019
Publisher: Springer Verlag
Book Volume: 11480 LNCS
Pages Range: 341-353
Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISBN: 9783030179526
DOI: 10.1007/978-3-030-17953-3_26
We examine how sparse feasible solutions of integer programs are, on average. Average case here means that we fix the constraint matrix and vary the right-hand side vectors. For a problem in standard form with m equations, there exist LP feasible solutions with at most m many nonzero entries. We show that under relatively mild assumptions, integer programs in standard form have feasible solutions with O(m) many nonzero entries, on average. Our proof uses ideas from the theory of groups, lattices, and Ehrhart polynomials. From our main theorem we obtain the best known upper bounds on the integer Carathéodory number provided that the determinants in the data are small.
APA:
Oertel, T., Paat, J., & Weismantel, R. (2019). Sparsity of Integer Solutions in the Average Case. In Andrea Lodi, Viswanath Nagarajan (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 341-353). Ann Arbor, MI, US: Springer Verlag.
MLA:
Oertel, Timm, Joseph Paat, and Robert Weismantel. "Sparsity of Integer Solutions in the Average Case." Proceedings of the 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019, Ann Arbor, MI Ed. Andrea Lodi, Viswanath Nagarajan, Springer Verlag, 2019. 341-353.
BibTeX: Download