Distances to lattice points in rational polyhedra

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

Preview	PDF - Accepted Post-Print Version Download (939kB) | Preview
	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