Improving the Cook et al. proximity bound given integral valued constraints

Celaya, Marcel ORCID: https://orcid.org/0000-0003-3480-4835, Kuhlmann, Stephan, Paat, Joseph and Weismantel, Robert 2022. Improving the Cook et al. proximity bound given integral valued constraints. Aardal, Karen and Sanità, Laura, eds. Integer Programming and Combinatorial Optimization. IPCO 2022., Vol. 13625. Lecture Notes in Computer Science, Cham: Springer, pp. 84-97. (10.1007/978-3-031-06901-7_7)

Full text not available from this repository.

Abstract

Consider a linear program of the form max{c⊤x:Ax≤b}, where A is an m×n integral matrix. In 1986 Cook, Gerards, Schrijver, and Tardos proved that, given an optimal solution x∗, if an optimal integral solution z∗ exists, then it may be chosen such that ∥x∗−z∗∥∞

Item Type:	Book Section
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Springer
ISBN:	9783031069017
Last Modified:	04 Jun 2024 13:14
URI:	https://orca.cardiff.ac.uk/id/eprint/157269

Actions (repository staff only)

Edit Item