David Manlove

I am Professor of Algorithms and Complexity at the School of Computing Science in the College of Science and Engineering at the University of Glasgow.

My research interests lie mainly in the field of Algorithms and Complexity. That means that I am interested in the design and analysis of efficient algorithms, and proving results about the extent to which a problem can be solved optimally or approximately using an efficient algorithm.

I am most interested in designing algorithms for matching problems, which involve allocating agents to commodities (e.g., junior doctors to hospitals, students to projects or kidney patients to donors) in the presence of "ordinal preferences" (e.g., a junior doctor might have first, second and third-choice hospitals, etc.) or "cardinal utilities" (e.g., real-valued weights that model the benefit of a kidney patient being assigned to a particular donor). The aim of a matching algorithm is to find an allocation that is optimal according to these ordinal preferences or cardinal utilities.

My research interests include:

• Matching problems, including stable matching and kidney exchange
• Algorithmic graph theory, including colouring, independence and domination in graphs
• Complexity and approximability of optimisation problems
• Integer programming models

A list of my publications and papers is available.

I am head of the Formal Analysis, Theory and Algorithms (FATA) research section in the School.

Research activities (current and recent)

• Book: "Algorithmics of Matching Under Preferences". The print edition is available to buy from the publisher or via Amazon.co.uk or Amazon.com. The e-edition and Kindle edition are also available to purchase and some sample material is available to view for free.
• Chair of KEP-SOFT:Software for Transnational Kidney Exchange Programmes (COST Innovators Grant IG15210)
• ACAC 2024 (invited speaker).
• Winter School on AI and TCS, IIT Jodhpur, December 2023 (invited speaker)
• Algorithms for kidney exchange
• Algorithms for allocating junior doctors to hospitals
• Algorithms for allocating students to projects and courses

Research funding (>£100k)

• EPSRC grant EP/X013618/1, KidneyAlgo: New Algorithms for UK and International Kidney Exchange (University of Glasgow principal investigator). Joint project with Durham University (grant EP/X01357X/1: Daniël Paulusma, principal investigator). 1 Apr 2023 – 31 Mar 2025 (£720k; University of Glasgow share £457k).
• COST Innovators Grant, KEP-SOFT: Software for Transnational Kidney Exchange Programmes (chair). 1 Nov 2021 – 31 Oct 2022 (£105k).
• EPSRC grant EP/P028306/1 , IP-MATCH: Integer Programming for Large and Complex Matching Problems (University of Glasgow principal investigator). Joint project with University of Edinburgh (grant EP/P029825/1: Sergio García Quiles, principal investigator; Jacek Gondzio and Jörg Kalcsics, co-investigators). 1 Nov 2017 – 30 Apr 2021 (£802k; University of Glasgow share £353k).
• EPSRC grant EP/K010042/1, Efficient Algorithms for Mechanism Design Without Monetary Transfer (University of Glasgow principal investigator). Joint project with University of Liverpool (grant EP/K01000X/1: Piotr Krysta, principal investigator; Giorgos Christodoulou, co-investigator; and Paul Goldberg, co-investigator). 6 June 2013 – 5 June 2016 (£599k; University of Glasgow share £269k). Final summary.
• NHS Blood and Transplant, Optimising options and strategies for living donor kidney transplantation for incompatible donor-recipient pairs (co-investigator). 1 January 2012 – 30 June 2013 (£151k).
• EPSRC grant EP/E011993/1, MATCH-UP: Matching Under Preferences - Algorithms and Complexity (co-investigator). 1 June 2007 – 30 June 2010 (£324k). Final summary.
• Royal Society of Edinburgh / Scottish Executive Personal Research Fellowship, Efficient Algorithms for Matching Problems. 1 October 2003 – 30 September 2006 (>£100k).

Researchers (current and former)

Current Researchers:

• Rachael Colley (Research Associate, started August 2023)
• William Pettersson (Research Software Engineer, started July 2023)
• Danielius Šukys (PhD student, started October 2024)
• Frederik Glitzner (PhD student, started October 2023)
• José Rodríguez Bacallado (PhD student, started October 2022)
• Fabricio Mendoza Granada (PhD student, started February 2022)

Former Research Assistants / Research Associates:

• William Pettersson (Research Associate), Nov 2017 - Oct 2020
• Baharak Rastegari (Research Associate), Jun 2013 – Jun 2016
• James Trimble (Research Assistant), Jan 2015 – Mar 2016
• Gregg O’Malley (Research Associate), Apr 2010 – Jun 2013
• Péter Biró (Research Assistant), Jun 2007 - Sep 2010

Completed Research Students (first supervisor):

• Michael McKay, PhD, Oct 2018 - Jan 2023, graduated Jun 2023
  Thesis: Algorithmic aspects of fixed-size coalition formation
• James Trimble, PhD, Oct 2016 - Dec 2022 (p/t), graduated Jun 2023 (jointly supervised with Patrick Prosser)
  Thesis: Partitioning algorithms for induced subgraph problems
• Frances Cooper, PhD, Oct 2015 - Aug 2020, graduated Nov 2020
  Thesis: Fair and large stable matchings in the stable marriage and student-project allocation problems
• Sofiat Olaosebikan, PhD, Oct 2016 - Mar 2020, graduated Dec 2021
  Thesis: The Student-Project Allocation Problem: Structure and Algorithms
• Iain McBride, PhD, Oct 2011 - Sep 2015, graduated Apr 2016
  Thesis: Complexity Results and Integer Programming Models for Hospitals / Residents Problem Variants
• Augustine Kwanashie, PhD, Oct 2011 - Mar 2015, graduated Dec 2015
  Thesis: Efficient Algorithms for Optimal Matching Problems Under Preferences
• Colin Sng, PhD, Oct 2004 - Apr 2008, graduated Jul 2008
  Thesis: Efficient Algorithms for Bipartite Matching Problems with Preferences
• Gregg O'Malley, PhD, Oct 2003 - Sep 2007, graduated Jul 2008
  Thesis: Algorithmic Aspects of Stable Matching Problems
• David Abraham, MSc, Oct 2002 - Sep 2003, graduated Jul 2004
  Thesis: Algorithmics of Two-sided Matching Problems

Other former Research Students (not first supervisor)

• Ágnes Cseh (Visiting Research Student), Feb - Jul 2014, graduated Dec 2015
  • Thesis: Complexity and algorithms in matching problems under preferences
• Eric McDermid (Research Student, second supervisor), PhD, Jun 2007 – May 2010, graduated Dec 2011
  • Thesis: A Structural Approach to Matching Problems with Preferences
• Chris Unsworth (Research Student, second supervisor), PhD, Oct 2004 – Jun 2008, graduated Dec 2008
  • Thesis: A specialised constraint approach for stable matching problems
• Sandy Scott (Research Student, second supervisor), PhD, Oct 2001 – Jul 2004, graduated Jul 2005
  • Thesis: A Study of Stable Marriage Problems with Ties

During academic year 2023/24, I will be teaching:

• Algorithmics II (H) (Hons / MSc elective, Semester 1).

Other previous teaching responsibilities have included:

• Web Application Development 2 (lectures, examples classes and lab sessions).
• Algorithmic Foundations 2 (tutorials and preparation of course materials).
• Algorithmics 3 (lectures, tutorials and lab sessions).
• Java Programming component of the MSc/MRes CS+ induction week.
• Programming (lectures, tutorials and lab sessions).
• Level 3 team, Level 4 individual and MSc individual projects.

Administration

Current responsibilities within the School:

• FATA Section Head
• adviser of studies

Previous responsibilities:

• Convenor of Research Student Committee
• member of Senate
• School engagement lead
• Level 4 year head
• membership of the School's Learning and Teaching Committee
• Level 3 projects coordinator
• representing the Department on the Faculty of Information and Mathematical Sciences Library Committee

External Service

• External examiner for the University of Warwick's undergraduate degree programmes (BSc/MEng) in Computer Science and Discrete Mathematics
• Editor of Theoretical Computer Science
• Associate Editor of Journal of Mechanism and Institution Design
• Member of the Steering Committee of MATCH-UP: the International Workshop on Matching Under Preferences
• PC membership: ADT 2024, SAGT 2024, MATCH-UP 2024, SAGT 2023, MATCH-UP 2022, IWOCA 2022, ADT 2021, SAGT 2020, CSR 2020, SAGT 2019, MATCH-UP 2019, WINE 2018, SAGT 2018, ACM EC 2018 (SPC), EXPLORE 2017, SAGT 2016, CP 2016, EXPLORE 2016, AAAI 2016, MATCH-UP 2015 (co-chair), EXPLORE 2015, MATCH-UP 2012, WINE 2012, MATCH-UP 2008

• Born in Edinburgh, 1974.
• Aug 1986-Jun 1992: Attended James Gillespie's High School, Edinburgh.
• Oct 1992-Jun 1995: Read for the BA in Mathematics and Computation at St Hugh's College, University of Oxford.
• Oct 1995-Jun 1998: Research for a PhD in Computing Science, University of Glasgow (supervisor: Dr Rob Irving).
• Oct 1998-Sep 2000: Research Assistant in Computing Science, University of Glasgow, working on the EPSRC-funded Stable Matching Algorithms research project.
• Oct 2000-Jul 2009: Lecturer in Computing Science, University of Glasgow.
• Oct 2003-Sep 2006: Held a Royal Society of Edinburgh / Scottish Executive Personal Research Fellowship.
• Aug 2009-Jul 2018: Senior Lecturer in Computing Science, University of Glasgow.
• Aug 2018-: Professor of Algorithms and Complexity, University of Glasgow.
• Jun 2019: Received the SICSA Supervisor of the Year award for 2019.
• Nov 2019: Awarded the Lord Kelvin Medal by the Royal Society of Edinburgh.

I stay in Linlithgow, a town in West Lothian.

Address:       Professor David Manlove MA PhD PGCAP FHEA
                       School of Computing Science
                       Sir Alwyn Williams Building
                       University of Glasgow
                       Glasgow G12 8QQ
                       UK

Office:            S151
Telephone:   +44 (0)141 330 2794
Email:             Firstname.Surname@Glasgow.ac.uk