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

Distances to lattice points in rational polyhedra

Williams, Aled 2022. Distances to lattice points in rational polyhedra. PhD Thesis, Cardiff University.
Item availability restricted.

[thumbnail of Aled Williams Thesis-January 2022.pdf]
Preview
PDF - Accepted Post-Print Version
Download (939kB) | Preview
[thumbnail of Cardiff University Electronic Publication Form] PDF (Cardiff University Electronic Publication Form) - Supplemental Material
Restricted to Repository staff only

Download (211kB)

Abstract

Let a ∈ Z n >0 , n ≥ 2 , gcd(a) := gcd(a1 , . . . , an ) = 1, b ∈ Z≥0 and denote by k · k∞ the ℓ∞-norm. Consider the knapsack polytope P(a, b) = { x ∈ R n ≥0 : a T x = b and assume that P(a, b) ∩ Z n 6= ; holds. The main result of this thesis states that for any vertex x ∗ of the knapsack polytope P(a, b) there exists a feasible integer point z ∗ ∈ P(a, b) such that, denoting by s the size of the support of z ∗ , i.e. the number of nonzero components in z ∗ and upon assuming s > 0 , the inequality kx ∗ − z ∗ k∞ 2 s−1 s < kak∞ holds. This inequality may be viewed as a transference result which allows strengthening the best known distance (proximity) bounds if integer points are not sparse and, vice versa, strengthening the best known sparsity bounds if feasible integer points are sufficiently far from a vertex of the knapsack polytope. In particular, this bound provides an exponential in s improvement on the previously best known distance bounds in the knapsack scenario. Further, when considering general integer linear programs, we show that a resembling inequality holds for vertices of Gomory’s corner polyhedra [49, 96]. In addition, we provide several refinements of the known distance and support bounds under additional assumptions

Item Type: Thesis (PhD)
Date Type: Completion
Status: Unpublished
Schools: Mathematics
Date of First Compliant Deposit: 11 February 2022
Last Modified: 11 Mar 2023 02:31
URI: https://orca.cardiff.ac.uk/id/eprint/147337

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics