Aled Williams
Research student, School of Mathematics
- williamsae13@cardiff.ac.uk
- Room M/1.10b, 21-23 Senghennydd Road, Cathays, Cardiff, CF24 4AG
Overview
Research Group
Operational Research Group and Mathematical Analysis Research Group
Research
Distances to Lattice Points in Rational Polyhedra
Research
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.
