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 |