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

Distance-sparsity transference for vertices of corner polyhedra

Aliev, Iskander, Celaya, Marcel, Henk, Martin and Williams, Aled 2020. Distance-sparsity transference for vertices of corner polyhedra. SIAM Journal on Optimization

[img]
Preview
PDF - Accepted Post-Print Version
Download (453kB) | Preview

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
Status: In Press
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: 25 Nov 2020 16:46
URI: http://orca.cf.ac.uk/id/eprint/136066

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics