Skip to content
 Aled Williams

Aled Williams

Research student, School of Mathematics

Email:
williamsae13@cardiff.ac.uk
Location:
M/1.10b, 21-23 Senghennydd Road, Cathays, Cardiff, CF24 4AG

Research Group

Operational Research Group and Mathematical Analysis Research Group

Research

Distances to Lattice Points in Rational Polyhedra

Research interests

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

Teaching

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

Thesis

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.