We recently sat down with Dr Meike Neuwohner, a talented mathematician who joined our department this year. Having completed her PhD at the University of Bonn, she’s now diving deep into research at LSE. We discussed her work, her experiences in London, and her passion for numbers.

Hi Meike, thanks for joining us. Let’s start with a bit about yourself. Where are you from, and where did you study for your degrees? 

I grew up in a village in Germany called Koslar, part of a small town called Jülich not too far from Aachen. For my studies, I went to the University of Bonn. I stayed there for my Bachelor’s, master’s and PhD.

How have you found moving to London from Bonn?

I’m finding it surprisingly nice! I was a bit worried about moving to a big city because I like nature and I enjoy peace, but London is surprisingly green. Living in a big city also has its benefits. For example, there is a good range of museums you can visit for free, and there are many more climbing gyms here than in Bonn. I have also found that people at LSE are friendly, and the environment is more relaxed. I also benefit from hearing talks from people in different areas of maths, allowing me to learn something new.

Did you always know you wanted to go into Maths? 

Well, not always. When I was a kid, I liked animals so I thought maybe I would become a vet. When I was in fifth grade, my maths teacher handed out exercise sheets for the Maths Olympiad and I started participating. It went relatively well, and I became part of a great community through the competition training. It was through these types of competitions that I became interested in maths; it was very satisfying when a problem came together, and you understood something new. Slowly, I became more and more sure that I wanted to go into mathematics.

So, tell me a bit about your current research and any open problems you find interesting.

Sure; first I’ll say a bit about what I did during my PhD because it’s a bit different from what I do now. In my PhD, I was looking at approximation algorithms. Specifically, I looked at the weighted k-set packing problem, which is defined as follows: you have a collection of sets, each with some positive weight, and each containing at most k elements. The goal is to find a subcollection which maximises the total weight, such that the sets in the subcollection are pairwise disjoint. For k at least three, finding such a collection is NP-hard.

I was working on approximation algorithms for this problem (meaning algorithms that don’t necessarily return the best possible solution, but which are guaranteed never to be too far off). The technique which has proved most effective when designing these is called “local search”. These algorithms start with any approximate solution – so they could start with the empty set. At each step, the algorithm adds some sets to the solution. When a new collection of sets is added to the solution, to maintain feasibility the algorithm must remove all the sets in the solution which have a non-empty intersection with the new sets. If the weight of the new sets is greater than the weight of the sets that must be removed, then the algorithm makes this swap, and this is called a local improvement. The algorithm stops at a locally optimum solution.

The approximation guarantee measures how close the final approximate solution is to the optimal solution. I was able to improve the approximation guarantee for this problem and draw some connections between the unweighted setting and the weighted setting. Most of my results were asymptotic, which means they only apply to very large values of k. There has been some recent progress, with some results which give better results for small values of k. However, it remains an open problem to find an exact formula for the approximation guarantee in terms of the size of the local improvements; it would be nice to see this solved.

I’ve now switched gears and I’m working on a project with Dr Ahmad Abdi. We are working towards the generalised Berge-Fulkerson conjecture. We are currently looking at some properties of lattices that we believe would be useful for solving this conjecture.

How did you find the transition from doing what you are familiar with in your PhD to what you are studying now?

I guess it’s always a little bit scary to change topics when you are very familiar with one area, but I’ve already learnt a lot and I’m finding this project interesting and fun. It’s always good to see something new and expand your horizons.

What advice do you have for an undergraduate student, or maybe even a postgraduate, who is thinking of going into research in mathematics?

Do it! It’s cool. I suppose occasionally it can be quite frustrating when you are thinking about a problem for a long time, and you can’t figure out a solution – it consumes a lot of your time. My advice would be to not let that throw you off; these things happen, and it doesn’t mean you’re bad at mathematics. Sometimes problems are just hard, and you can’t solve them, and that’s okay. It can help to take a break and go for a walk or a run. So, try hard, but don’t try too hard; there might be some problems you won’t be able to solve but there will be many that you can.