Computer Science - Approximation Algorithm for Clustering Problems

Supervisor: Dr Joachim Spoerhase

Supervisor bio: 

Dr Joachim Spoerhase is a Lecturer (Assistant Professor) at the School of Computer Science and Informatics at the University of Liverpool. His expertise lies in the design of algorithms, in particular approximation algorithms, for combinatorial optimisation problems such as clustering, network design and geometric optimisation problems. Before this, he held research positions at several institutions such as the  Max Planck Institute for Informatics (MPI-INF) in Germany, the Aalto University in Finland, and the University of Wroclaw in Poland. He obtained his habilitation in 2017 and received his PhD in 2010 from the University of Würzburg, Germany.

Email: joachim.spoerhase@liverpool.ac.uk

School: School of Computer Science and Informatics 

Department: Computer Science

Module code: COMP298

Suitable for students of: Computer Science, Mathematics

Desirable experience/requirements: 

Basic modules in algorithm design, theoretical computer science, and discrete mathematics are a prerequisite. Ideally, you have taken advanced modules in algorithms such as approximation algorithms. You should have a certain mathematical maturity, which includes autonomously working on mathematical problems, rigorously proving theorems. I recommend you take a look at my list of selected publications to get an impression.

Places available: 1

Start date: Session 1 (15th June 2026)

Project length: 4 weeks 

Virtual option: No

Hybrid option: No

Project description: 

Clustering refers to the fundamental task of partitioning a set of objects into groups (clusters) of pairwise similar objects. It has numerous applications in many areas such as data analysis, machine learning, and operations research. In this project, we will study clustering problems from a combinatorial optimization point of view. For example, in the well-known k-Median problem the task is to select k cluster centers (each representing a cluster) so that the sum of distances of the input data points to their nearest center is minimized. We will design algorithms for variants of such problems and analyze them rigorously. A basic challenge is that most clustering problems (such as k-Median) are NP-hard, which means that no efficient algorithm is known that computes an optimal solution for any input, and it is widely believed that no such algorithm exists. We will therefore study approximation algorithms, which may not compute an optimal solution but are guaranteed to compute a solution that is within a bounded factor of optimal (quality guarantee). For example, a 3-approximation algorithm for k-Median always outputs a solution where the sum of distances is at most three times as large as in the (unknown) optimal solution. If you are excited about topics such as the design and analysis of algorithms, theoretical computer science, combinatorial optimization, or discrete mathematics then this project could be a good choice for you. In this case, I recommend you to have a look at my list of publications to get an impression about the research we will be doing.

Additional requirements: N/A