Aliev, Iskander ORCID: https://orcid.org/0000-0002-2206-9207, Celaya, Marcel, Henk, Martin and Williams, Aled 2021. Distance-sparsity transference for vertices of corner polyhedra. SIAM Journal on Optimization 31 (1) 10.1137/20M1353228 |
Preview |
PDF
- Accepted Post-Print Version
Download (453kB) | Preview |
Official URL: https://doi.org/10.1137/20M1353228
Abstract
We obtain a transference bound for vertices of corner polyhedra that connects two well-established areas of research: proximity and sparsity of solutions to integer programs. In the knapsack scenario, it implies an exponential in size of support improvement on previously known proximity estimates. In addition, for general integer linear programs we obtain a resembling result that connects the minimum absolute nonzero entry of an optimal solution with the size of its support.
Item Type: | Article |
---|---|
Date Type: | Published Online |
Status: | Published |
Schools: | Mathematics |
Subjects: | Q Science > QA Mathematics |
Publisher: | Society for Industrial and Applied Mathematics |
ISSN: | 1052-6234 |
Date of First Compliant Deposit: | 2 November 2020 |
Date of Acceptance: | 21 October 2020 |
Last Modified: | 08 Nov 2023 06:01 |
URI: | https://orca.cardiff.ac.uk/id/eprint/136066 |
Citation Data
Cited 3 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
Edit Item |