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
Item availability restricted.

[img] PDF - Accepted Post-Print Version
Restricted to Repository staff only until 13 April 2020 due to copyright restrictions.

Download (275kB)

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: 21 May 2019 16:14
URI: http://orca.cf.ac.uk/id/eprint/121368

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics