Algorithms: Complexity and Engineering (ACE)

Introduction

Research undertaken within the ACE theme is wide-ranging. The goals are, broadly, to understand and quantify the computational resources required to solve a problem. A closely related aim is to understand the power and limitations of models of computation. We also use our understanding to develop software that efficiently uses resources to solve demanding computational problems.

Staff Members

PhD Students

  • Laith Ali Abdulsahib - Space-efficient representations of Boolean functions
  • Aeshah Alsughayyir - Energy-efficient cloud scheduling
  • Yasemin Asan - Mining sequential patterns from uncertain data
  • Anastasia Ioannou - Petri nets and fault detection
  • Rafael Ktistakis - Compact data structures for sequence prediction
  • Aisha Mashraqi - Routing in wireless networks
  • Andreas Poyias - Compact data structures for frequent pattern mining

Recently Completed PhD Theses

Research Overview

We work in a number of areas including: approximation and online algorithms, data structures, efficient algorithms, algorithms for algebraic and geometric problems, graph and network algorithms, scheduling algorithms, and decidability. We also look at practical aspects and applications of theory, in particular algorithm engineering, which deals with the practical applications and performance of algorithms.

Research Areas

Approximation algorithms

Many combinatorial optimisation problems are NP-hard, and we cannot hope for efficient algorithms that produce optimal solutions for every instance. Approximation algorithms produce solutions to optimisation problems whose objective value always lies within a certain factor (called the approximation ratio) of the optimal solution. We study approximation algorithms for many different types of combinatorial optimisation problems, including geometric problems, graph problems and network problems. Many of these problems are motivated by applications in communication networks.

Bin packing

Bin packing is a classical and well-studied problem in combinatorial optimization. In this problem, items with various sizes need to be packed into bins, and the goal is to minimize the total number of bins used. For the online version, we have recently given an algorithm with optimal absolute competitive ratio, and we are currently working on the asymptotic performance ratio. We also consider this problem in two and three dimensions, where rectangles or boxes need to be packed.

Complexity of Algebraic Structures

We consider various types of algebraic structure (such as groups and semigroups) and consider the possibilities for efficient computation in such systems. A key issue is how one represents the structure and this is often done using concepts from theoretical computer science such as finite automata. In some cases one can develop algorithms based on such representations and in others show that no algorithms can exist.

Computing under uncertainty

We consider settings where instead of precise input data, only estimates (e.g. intervals) of the input values are known initially. Exact information about the value of an input item can be obtained using a query. The goal is to minimise the number of queries needed until sufficient information has been obtained for solving the problem. Algorithms are evaluated in the framework of competitive analysis. Problems we have studied in this setting include convex hull, maximal points, minimum spanning tree, minimum multi-cut and cheapest set.

Design and implementation of efficient data structures

We assume that we are given a kind of data, and a set of permitted operations on the data.  The objective is to pre-process the given data into a representation (the data structure) so that a long sequence of operations can be supported in an efficient manner.  "Efficiency" can mean the amount of CPU time taken to support an individual operation, or a sequence of operations, the amount of computer memory used by the data structure, or the CPU time taken during the pre-processing phase.  We aim to quantify the resource requirements mathematically, and prove upper and lower bounds on resource usage. The kind of data considered could be networks, strings of characters or geometric objects like 2D or 3D points, lines, boolean functions etc..  A recent line of work is to focus on succinct data structures, whose space usage is close to the information-theoretic minimum.

Online scheduling

In online scheduling, jobs need to be assigned to one or more machines without knowledge of future jobs. There is a vast number of variations of this problem, depending on the objective function, the number of machines, whether preemptions (or restarts) are allowed or not, and many other parameters. Recently a paper on scheduling jobs with fixed starting times was accepted to Algorithmica.

We also contribute to the Knowledge Discovery and Machine Learning working group.

Contact

Contact details for each staff member and most PhD students are available from their respective homepages.

For general enquiries about the ACE theme, please contact Thomas Erlebach. We welcome enquiries from industry about potential applications of algorithms.

Share this page:

Contact Us

Admissions Enquiries:
BSc: +44 (0) 116 252 5280
MSc: +44 (0) 116 252 2265
E: BSc  seadmissions@le.ac.uk
E: MSc  pgadmissions@le.ac.uk

Departmental Enquiries:
T: +44 (0) 116 252 2129/3887
F: +44 (0) 116 252 3604
E: csadmin@mcs.le.ac.uk

Dept of Informatics
University of Leicester
Leicester, LE1 7RH
United Kingdom

Accessibility

DisabledGo logo

The University of Leicester is committed to equal access to our facilities. DisabledGo has a detailed accessibility guide for the Informatics Building.