Algorithms

The Algorithms Group focusses on designing and analysing algorithms that solve computational problems efficiently. Group members combine techniques from computer science, discrete mathematics, probability theory and other fields in algorithms research.

Algorithms research group staff members
Off

Research Themes 

Theory of Bio-Inspired Algorithms

This topic covers general-purpose optimisation paradigms that draw inspiration from biological systems. Evolutionary algorithms mimic Darwinian principles such as survival of the fittest to artificially evolve candidate solutions for optimisation and design problems. Swarm intelligence paradigms such as ant colony optimisation or particle swarm optimisation are based on the collective intelligence of animal swarms. We work on providing a theoretical foundation for understanding the working principles of these heuristic algorithms through quantifying how quickly they find satisfactory solutions for various problems. This exposes how performance depends on algorithmic parameters and design choices, and helps to design better bio-inspired optimisation algorithms.

Numerical Algorithms

There are three themes in the 'Numerical Algorithms' research group. These are geometric modelling, image deblurring and variable selection for high dimensional statistical modelling. Although these themes appear initially to be unrelated, they all involve the solution of problems that are unstable because  a small change in the data causes a large change in the result. Advanced methods using computational linear algebra are therefore used to obtain computationally reliable solutions to these problems, but the methods differ because the governing
equations for the three problems are different. The methods used include regularisation and structure-preserving matrix methods applied to algorithms in algebraic geometry.

Parameterized Algorithms

Parameterized algorithms are exact algorithms for computational hard problems that exploit the structuredness of real-world instances to solve certain instances of these problems much more efficiently. Since almost every real-world instance comes with more information than just its input size in bits, the parameterized approach allows a much more fine-grained analysis of the complexity of computational problems than the classical P vs NP-framework. Our group employs the parameterized approach for a wide range of problems in computer science such as satisfiability, constraint satisfaction, integer linear programming, planning, and problems on graphs and networks.

Efficient Graph Algorithms

Graphs are everywhere. Typical examples include Facebook/Twitter, Internet, Web graphs and brain networks. Many such graphs are extremely large, and are constantly changing, which poses great challenges for efficiently analysing their structures. We aim to tackle these challenges through the design and analysis of graph algorithms in the modern computational models, including sublinear algorithms (e.g., property testing, streaming algorithms) that read or store only a small portion of the large input while still have provable performance guarantees, and dynamic algorithms that update efficiently the solution of a problem after dynamic changes over the graph.

    Research group members

    Academic staff

    Affiliated staff

    Research staff

    Research students

    Seminars

    Upcoming seminars

    Details to be confirmed 

    Past Seminars

    2019

    May 21st, 2019
    14:00-15:00
    In COM-108 - Ada Lovelace Room.

    Some recent advances in dynamic graph algorithms
    Presented by Sayan Bhattacharya (University of Warwick).

    February 25th, 2019
    13:00-14:00
    In COM-G12-Blue.

    Hierarchical clustering: Objective functions and new algorithms
    Presented by Varun Kanade (University of Oxford)

    February 15th, 2019
    14:00-15:00
    In COM-G22-Blue.

    Geometric Semantic Genetic Programming
    Presented by Alberto Moraglio (University of Exeter)

    2018

    November 27th, 2018
    15:00-16:00
    In COM-G25.

    Testing logically defined properties on graphs of bounded degree
    Presented by Isolde Adler (University of Leeds)

    November 15th, 2018
    14:00-15:00
    In the Ada Lovelace Room.

    Algorithms for Out- and In-Branchings in Digraphs
    Presented by Gregory Gutin (Royal Holloway).

    November 19th, 2018
    14:00-15:00
    In the Ada Lovelace Room.

    Colouring Diamond-free Graphs
    Presented by Konrad Dabrowski (University of Durham)

    October 29th, 2018
    14:00-15:00
    In the Ada Lovelace Room.

    Finding Small Cuts in Dense Graphs
    Presented by Thomas Sauerwald (Cambridge University)

    October 17th, 2018
    15:00-16:00
    In the Ada Lovelace Room.

    Recent Advances on the Parameterized Complexity of Integer Linear Programming
    Presented by Sebastian Ordyniak.

    October 8th, 2018
    16:00-17:00
    In the Ada Lovelace Room.

    Graph Property Testing and Random Order Streams
    Presented by Pan Peng.

    July 27th, 2018
    15:00-16:00
    In the Ada Lovelace Room.

    Sunflowers and Quasi-sunflowers from Randomness Extractors
    Presented by Jiapeng Zhang (UC San Diego).

    July 9th, 2018
    12:00-13:00
    In COM-G25.

    Memetic Algorithms Beat Evolutionary Algorithms on the Class of Hurdle Problems
    Presented by Phan Trung Hai Nguyen (University of Birmingham).

    June 28th, 2018
    11:00-12:00
    In the Ada Lovelace Room.

    Spectral Sparsification and its Applications
    Presented by Dr. He Sun (University of Edinburgh).

    May 23rd, 2018
    11:00-12:00
    In the Ada Lovelace Room.

    Exact and Hybrid Approaches for Packing While Traveling and the Traveling Thief Problem
    Presented by Prof. Frank Neumann (University of Adelaide).

    Flagship institutes

    The University’s four flagship institutes bring together our key strengths to tackle global issues, turning interdisciplinary and translational research into real-world solutions.