Oertel, Timm ORCID: https://orcid.org/0000-0001-5720-8978, Paat, Joseph and Weismantel, Robert 2019. Sparsity of integer solutions in the average case. Presented at: 20th Conference on Integer Programming and Combinatorial Optimization (IPCO XX), Ann Arbor, MI, USA, 22-24 May 2019. Published in: Lodi, Andrea and Nagarajan, Viswanath eds. Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings. Lecture Notes in Computer Science. Lecture Notes in Computer Science Springer Verlag, pp. 341-353. 10.1007/978-3-030-17953-3_26 |
Preview |
PDF
- Accepted Post-Print Version
Download (275kB) | Preview |
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.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Date Type: | Published Online |
Status: | Published |
Schools: | Mathematics |
Publisher: | Springer Verlag |
Related URLs: | |
Date of First Compliant Deposit: | 16 April 2019 |
Date of Acceptance: | 1 April 2019 |
Last Modified: | 25 Oct 2022 14:00 |
URI: | https://orca.cardiff.ac.uk/id/eprint/121368 |
Citation Data
Cited 6 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
Edit Item |