Skip to main content
 Aled Williams

Aled Williams

Research student, School of Mathematics

Room M/1.10b, 21-23 Senghennydd Road, Cathays, Cardiff, CF24 4AG


Research Group

Operational Research Group and Mathematical Analysis Research Group


Distances to Lattice Points in Rational Polyhedra


Research interests

  • Integer Optimisation
  • Discrete Mathematics (Geometry of Numbers, Discrete Geometry)
  • Number Theory
  • Crypography


  • Geometry (MA1004)
  • Elementary Differential Equations (MA1001)
  • Foundations 1 (MA1005)
  • Finance 1: Financial Markets and Corporate Financial Management (MA1801)


Distances to Lattice Points in Rational Polyhedra

 It is well known that finding a solution to an integer linear program (ILP) in general is NP-complete. Despite this one can obtain an approximation within polynomial time by solving its related linear program (LP). Because of this it should come as no surprise that a central problem within this research domain is to estimate the distance from an approximate solution (obtained from solving the LP) to some nearby feasible integer solution (that solves the ILP). We will use the term ‘(maximum) vertex distance’ to denote this distance. 

My thesis aims to find optimal worst case upper bounds on the (maximum) vertex distance using some fundametal characteristics of the underlying integral constraint matrix.