Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Sparsity of integer solutions in the average case

Oertel, Timm, 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 Springer Verlag, pp. 341-353. 10.1007/978-3-030-17953-3_26

PDF - Accepted Post-Print Version
Download (275kB) | Preview


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: 13 Apr 2020 02:05

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics