Sparsity of Integer Solutions in the Average Case

Oertel T, Paat J, Weismantel R (2019)

Publication Type: Conference contribution

Publication year: 2019

Journal

Lecture Notes in Computer Science Springer Verlag

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)

Event location: Ann Arbor, MI US

ISBN: 9783030179526

DOI: 10.1007/978-3-030-17953-3_26

Abstract

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.

Authors with CRIS profile

Timm Oertel

Additional Organisation(s)

Professur für Mathematische Analyse von Daten (Data Analytics)

Involved external institutions

Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich CH Switzerland (CH) Cardiff University GB United Kingdom (GB)

How to cite

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