Sparsity of integer solutions in the average case

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:	Organisation Organisation
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