Publications and papers

Links to the Postprint versions of the published papers are also included here (with permission from the relevant publishers) for those who do not have online access to the relevant journals / conference proceedings.

Book

Book chapters

Edited journal issues

Journal papers

  1. The Stable Roommates problem with short lists, with Ágnes Cseh and Rob Irving.  To appear in Theory of Computing Systems.
  2. Matchings with lower quotas: Algorithms and complexity, with Ashwin Arulselvan, Ágnes Cseh, Martin Groβ and Jannik Matuschke.  To appear in Algorithmica.
  3. “Almost stable” matchings in the Hospitals / Residents problem with Couples, with Iain McBride and James Trimble.  Constraints, 22 (1) : 50-72, 2017 (Open Access).  Received Distinguished Paper Award at CP 2016.  Postprint.  Associated research data.
  4. Stable matchings of teachers to schools, with Katarína Cechlárová, Tamás Fleiner and Iain McBride.  Theoretical Computer Science, 653 : 15-25, 2016 (Open Access).
  5. Pareto Optimal Matchings in Many-to-Many Markets with Ties, with Katarína Cechlárová, Pavlos Eirinakis, Tamás Fleiner, Dimitrios Magos, Ioannis Mourtos, Eva Ocel’áková and Baharak Rastegari.  Theory of Computing Systems, 59 (4) : 700–721, 2016 (Open Access).  Postprint.
  6. Stable marriage and roommates problems with restricted edges: Complexity and approximability with Ágnes Cseh.  Discrete Optimization, 20 : 62-89, 2016 (Open Access).  Postprint.
  7. Modelling practical placement of trainee teachers to schools, with Katarína Cechlárová, Tamás Fleiner, Iain McBride and Eva Potpinková.  Central European Journal of Operations Research, 23 (3) : 547-562, 2015.  Postprint.
  8. Paired and altruistic kidney donation in the UK: Algorithms and experimentation, with Gregg O’Malley.  ACM Journal of Experimental Algorithmics, volume 19, number 2, article 2.6, 21 pages, 2014.  Postprint.
  9. “Almost stable” matchings in the Roommates problem with bounded lists, with Péter Biró and Eric McDermid.  Theoretical Computer Science, 432 : 10-20, 2012.  Postprint.
  10. An algorithm for a super-stable roommates problem, with Tamás Fleiner and Rob Irving.  Theoretical Computer Science, 412 (50) : 7059-7065, 2011.  Postprint.
  11. The College Admissions Problem with Lower and Common Quotas, with Péter Biró, Tamás Fleiner and Rob Irving.  Theoretical Computer Science, 411 : 3136-3153, 2010.  The full version of this paper is available as Technical Report no. TR-2009-303, Department of Computing Science, University of Glasgow, 2009.  Postprint.
  12. Keeping partners together: Algorithmic results for the Hospitals / Residents problem with couples, with Eric McDermid.  Journal of Combinatorial Optimization, 19 (3) : 279-303, 2010.  Postprint.  Errata.
  13. Size versus stability in the Marriage problem, with Péter Biró and Shubham Mittal.  Theoretical Computer Science, 411 : 1828-1841, 2010.  Postprint.
  14. Popular matchings in the weighted capacitated house allocation problem (journal version), with Colin Sng.  Journal of Discrete Algorithms, 8:102-116, 2010.  Postprint.
  15. Maximum weight cycle packing in directed graphs, with application to kidney exchange programs, with Péter Biró and Romeo Rizzi.  Discrete Mathematics, Algorithms and Applications, 1 (4) : 499-517, 2009.  Postprint.
  16. Finding large stable matchings, with Rob Irving.  ACM Journal of Experimental Algorithmics, volume 14, section 1, article 2, 30 pages, 2009.  Postprint.
  17. Vertex and edge covers with clustering properties: complexity and algorithms, with Henning Fernau.  Journal of Discrete Algorithms, 7 (2) : 149-167, 2009.  Postprint.
  18. Stable marriage with ties and bounded length preference lists, with Rob Irving and Gregg O’Malley.  Journal of Discrete Algorithms, 7 (2) : 213-219, 2009.  Postprint.
  19. The Stable Roommates problem with Globally-Ranked Pairs, with David Abraham, Ariel Levavi and Gregg O’Malley.  Internet Mathematics 5(4):493-515, 2008.  Postprint.
  20. The Stable Marriage Problem with Master Preference Lists, with Rob Irving and Sandy Scott.  Discrete Applied Mathematics, 156 (15) : 2959-2977, 2008.  Postprint.
  21. Student-project allocation with preferences over projects, with Gregg O’Malley.  Journal of Discrete Algorithms, 6 : 553-560, 2008.  Postprint.
  22. Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems, with Rob Irving.  Journal of Combinatorial Optimization, 16 (3) : 279-292, 2008.  Postprint.
  23. Efficient algorithms for generalized stable marriage and roommates problems, with Tamás Fleiner and Rob Irving.  Theoretical Computer Science, 381 (1-3) : 162-176, 2007.  Postprint.
  24. Two algorithms for the Student-Project Allocation problem, with David Abraham and Rob Irving.  Journal of Discrete Algorithms, 5 (1) :73-90, 2007.  Postprint.
  25. The Exchange-Stable Marriage Problem, with Katarína Cechlárová.  Discrete Applied Mathematics, 152 (1-3) : 109-122, 2005.  Postprint.
  26. On the approximability of the maximum induced matching problem, with William Duckworth and Michele Zito.  Journal of Discrete Algorithms, 3(1):79-91, 2005.  Postprint.
  27. Combined Super-/Substring and Super-/Subsequence Problems, with Martin Middendorf.  Theoretical Computer Science, 320 (2-3) : 247-267, 2004.  Postprint.
  28. Approximability results for stable marriage problems with ties, with Magnús Halldórsson, Rob Irving, Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita and Sandy Scott.  Theoretical Computer Science, 306 (1-3) : 431-447, 2003.  Postprint.
  29. The Stable Roommates Problem with Ties, with Rob Irving.  Journal of Algorithms, 43:85-105, 2002.  Errata.  Postprint.
  30. Hard variants of stable marriage, with Rob Irving, Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita.  Theoretical Computer Science, 276 (1-2) : 261-279, 2002.  Postprint.
  31. The structure of stable marriage with indifference.  Discrete Applied Mathematics, 122 (1-3) : 167-181, 2002.  Postprint.
  32. On the algorithmic complexity of twelve covering and independence parameters of graphs.  Discrete Applied Mathematics, 91 (1-3) : 155-175, 1999.  Postprint.
  33. The b-chromatic number of a graph, with Rob Irving.  Discrete Applied Mathematics, 91 (1-3) : 127-141, 1999.  Postprint.

Conference papers

  1. The Stable Roommates problem with short lists, with Ágnes Cseh and Rob Irving.  In Proceedings of SAGT 2016: the 9th International Symposium on Algorithmic Game Theory, volume 9928 of Lecture Notes in Computer Science, pages 207-219, Springer, 2016.  Postprint.  The full version of this paper is available as Technical Report no. 1605.04609, Computing Research Repository, Cornell University Library, 2016.
  2. Position-indexed formulations for kidney exchange, with John P. Dickerson, Ben Plaut, Tuomas Sandholm and James Trimble.  In Proceedings of EC 2016: the 17th ACM Conference on Economics and Computation, pages 25-42, ACM, 2016.  Postprint.  The full version of this paper is available as Technical Report no. 1606.01623, Computing Research Repository, Cornell University Library, 2016.
  3. Preference elicitation in matching markets via interviews: A study of offline benchmarks, with Baharak Rastegari and Paul Goldberg.  In Proceedings of AAMAS 2016: the 15th International Conference on Autonomous Agents and Multi-Agent Systems, pages 1393-1394, IFAAMAS, 2016.  Postprint.  The full version of this paper is available as Technical Report no. 1602.04792, Computing Research Repository, Cornell University Library, 2016.
  4. Many-to-one matchings with lower quotas: Algorithms and complexity, with Ashwin Arulselvan, Ágnes Cseh, Martin Groβ and Jannik Matuschke.  In Proceedings of ISAAC 2015: the 26th International Symposium on Algorithms and Computation, volume 9472 of Lecture Notes in Computer Science, pages 176-187, Springer, 2015 (Open Access).  Postprint.  The full version of this paper is available as Technical Report no. 1412.0325, Computing Research Repository, Cornell University Library, 2015.
  5. Pareto Optimal Matchings in Many-to-Many Markets with Ties, with Katarína Cechlárová, Pavlos Eirinakis, Tamás Fleiner, Dimitrios Magos, Ioannis Mourtos, Eva Ocel’áková and Baharak Rastegari.  In Proceedings of SAGT 2015: the 8th International Symposium on Algorithmic Game Theory, volume 9347 of Lecture Notes in Computer Science, pages 27-39, Springer, 2015.  Postprint.  The full version of this paper is available as Technical Report no. 1507.02866, Computing Research Repository, Cornell University Library, 2015.
  6. Stable marriage and roommates problems with restricted edges: Complexity and approximability, with Ágnes Cseh.  In Proceedings of SAGT 2015: the 8th International Symposium on Algorithmic Game Theory, volume 9347 of Lecture Notes in Computer Science, pages 15-26, Springer, 2015.  Postprint. The full version of this paper is available as Technical Report no. 1412.0271, Computing Research Repository, Cornell University Library, 2014.
  7. Profile-based optimal matchings in the Student-Project Allocation problem, with Augustine Kwanashie, Rob Irving and Colin Sng.  In Proceedings of IWOCA 2014: the 25th International Workshop on Combinatorial Algorithms, volume 8986 of Lecture Notes in Computer Science, pages 213-225, Springer, 2015.  Postprint.  The full version of this paper is available as Technical Report no. 1403.0751, Computing Research Repository, Cornell University Library, 2014.  Associated research data.
  8. Size versus truthfulness in the House Allocation problem, with Piotr Krysta, Baharak Rastegari and Jinshan Zhang.  In Proceedings of EC 2014: the 15th ACM Conference on Economics and Computation, pages 453-470, ACM, 2014.  Postprint.  The full version of this paper is available as Technical Report no. 1404.5245, Computing Research Repository, Cornell University Library, 2014.
  9. The Hospitals / Residents problem with Couples: Complexity and Integer Programming models, with Péter Biro and Iain McBride.  In Proceedings of SEA 2014: the 13th International Symposium on Experimental Algorithms, volume 8504 of Lecture Notes in Computer Science, pages 10-21, Springer, 2014.  Postprint.  Associated research data.  The full version of this paper is available as Technical Report no. 1308.4534, Computing Research Repository, Cornell University Library, 2013.
  10. An Integer Programming approach to the Hospitals / Residents problem with Ties, with Augustine Kwanashie.  In Proceedings of OR 2013: the International Conference on Operations Research, pages 263-269, Springer, 2014.  Postprint.  Associated research data.  The full version of this paper is available as Technical Report no. 1308.4064, Computing Research Repository, Cornell University Library, 2013.
  11. An Integer Programming Model for the Hospitals/Residents Problem with Couples, with Iain McBride.  In Proceedings of OR 2013: the International Conference on Operations Research, pages 293-299, Springer, 2014.  Postprint.  Associated research data.  The full version of this paper is available as Technical Report no. 1308.4534, Computing Research Repository, Cornell University Library, 2013.
  12. Socially Stable matchings in the Hospitals / Residents problem, with Georgios Askalidis, Nicole Immorlica, Augustine Kwanashie and Emmanouil Pountourakis.  In Proceedings of WADS 2013: the 13th Algorithms and Data Structures Symposium, volume 8037 of Lecture Notes in Computer Science, pages 85-96, Springer, 2013.  Postprint.  The full version of this paper is available as Technical Report no. 1303.2041, Computing Research Repository, Cornell University Library, 2013.
  13. Paired and altruistic kidney donation in the UK: Algorithms and experimentation, with Gregg O’Malley.  In Proceedings of SEA 2012: the 11th International Symposium on Experimental Algorithms, volume 7276 of Lecture Notes in Computer Science, pages 271-282, Springer, 2012.  Postprint.  The full version of this paper is available as Technical Report no. TR-2012-330, School of Computing Science, University of Glasgow, 2012.
  14. Popular matchings in the Marriage and Roommates problems, with Péter Biró and Rob Irving.  In Proceedings of CIAC 2010: the 7th International Conference on Algorithms and Complexity, volume 6078 of Lecture Notes in Computer Science, pages 97-108, Springer, 2010.  Postprint.  The full version of this paper is available as Technical Report no. TR-2009-306, Department of Computing Science, University of Glasgow, 2009.
  15. Size versus stability in the Marriage problem, with Péter Biró and Shubham Mittal.  In Proceedings of WAOA 2008: the 6th Workshop on Approximation and Online Algorithms, volume 5426 of Lecture Notes in Computer Science, pages 15-28, Springer, 2009.  Postprint.  The full version of this paper is available as Technical Report no. TR-2009-297, Department of Computing Science, University of Glasgow, 2009.
  16. The Stable Roommates problem with Globally-Ranked Pairs, with David Abraham, Ariel Levavi and Gregg O’Malley.  In Proceedings of WINE 2007: the 3rd International Workshop On Internet and Network Economics, volume 4858 of Lecture Notes in Computer Science, pages 431-444, Springer, 2007.  Postprint.  The full version of this paper is available as Technical Report no. TR-2007-257, Department of Computing Science, University of Glasgow, 2007.
  17. An 8/5-approximation algorithm for a hard variant of stable marriage, with Rob Irving.  In Proceedings of COCOON 2007: the 13th Annual International Computing and Combinatorics Conference, volume 4598 of Lecture Notes in Computer Science, pages 548–558, Springer, 2007.  Postprint.  Note: there is a mistake in the COCOON paper.  The correct performance guarantee for the approximation algorithm is 5/3.  See the full version of the paper, in Journal of Combinatorial Optimization, 16 (3) : 279-292, 2008.
  18. A Constraint Programming Approach to the Hospitals / Residents Problem, with Gregg O’Malley, Patrick Prosser and Chris Unsworth.  In Proceedings of CP-AI-OR 2007: the Fourth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, volume 4510 of Lecture Notes in Computer Science, pages 155-170, Springer, 2007.  Postprint.  The full version of this paper is available as Technical Report no. TR-2007-236, Department of Computing Science, University of Glasgow, 2007.
  19. Popular matchings in the Capacitated House Allocation problem, with Colin Sng.  In Proceedings of ESA 2006: the 14th Annual European Symposium on Algorithms, volume 4168 of Lecture Notes in Computer Science, pages 492-503, Springer, 2006.  Postprint.  The full version of this paper is available as Technical Report no. TR-2006-222, Department of Computing Science, University of Glasgow, 2006.
  20. “Almost stable” matchings in the Roommates problem, with David Abraham and Péter Biró.  In Proceedings of WAOA 2005: the 3rd Workshop on Approximation and Online Algorithms, volume 3879 of Lecture Notes in Computer Science, pages 1-14, Springer, 2006.  Postprint.
  21. Pareto Optimality in House Allocation Problems, with David Abraham, Katarína Cechlárová and Kurt Mehlhorn.  In Proceedings of ISAAC 2004: the 15th Annual International Symposium on Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages 3-15, Springer, 2004.  Postprint.  Some fonts were missing in the printing of the hard-copy version (but not the on-line version) of this paper.  Springer printed a corrected version in Proceedings of ISAAC 2005: the 16th Annual International Symposium on Algorithms and Computation, volume 3827 of Lecture Notes in Computer Science, pages 1163-1175, Springer, 2005.
  22. The Student-Project Allocation Problem, with David Abraham and Rob Irving. In Proceedings of ISAAC 2003: the 14th Annual International Symposium on Algorithms and Computation, volume 2906 of Lecture Notes in Computer Science, pages 474-484, Springer, 2003.  Postprint.  The full version of this paper appeared in Journal of Discrete Algorithms, 5 (1) :73-90, 2007.
  23. Strong Stability in the Hospitals / Residents Problem, with Rob Irving and Sandy Scott. In Proceedings of STACS 2003: the 20th International Symposium on Theoretical Aspects of Computer Science, volume 2607 of Lecture Notes in Computer Science, pages 439-450, Springer, 2003.  Postprint.  The full version of this paper is available as Technical Report no. TR-2002-123, Department of Computing Science, University of Glasgow, 2002 (revised May 2005).
  24. A Constraint Programming Approach to the Stable Marriage Problem, with Ian Gent, Rob Irving, Patrick Prosser and Barbara Smith. In Proceedings of CP '01: the 7th International Conference on Principles and Practice of Constraint Programming, volume 2239 of Lecture Notes in Computer Science, pages 225-239, Springer, 2001.  Postprint.
  25. The Hospitals/Residents Problem with Ties, with Rob Irving and Sandy Scott. In Proceedings of SWAT 2000: the 7th Scandinavian Workshop on Algorithm Theory, volume 1851 of Lecture Notes in Computer Science, pages 259-271. Springer, 2000.  Postprint.
  26. Stable marriage with incomplete lists and ties, with Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita. In Proceedings of ICALP '99: the 26th International Colloquium on Automata, Languages and Programming, volume 1644 of Lecture Notes in Computer Science, pages 443-452. Springer, 1999.  Postprint.

Workshop papers

  1. Pareto optimal matchings of students to courses in the presence of prerequisites, with Katarína Cechlárová and Bettina Klaus.  In Proceedings of COMSOC 2016: the 6th International Workshop on Computational Social Choice.  Postprint.
  2. Preference elicitation in matching markets via interviews: A study of offline benchmarks, with Baharak Rastegari and Paul Goldberg.  In Proceedings of EXPLORE 2016: the 3rd Workshop on Exploring Beyond the Worst Case in Computational Social Choice, 2016.  The full version of this paper is available as Technical Report no. 1602.04792, Computing Research Repository, Cornell University Library, 2016.  Postprint.
  3. An algorithm for a super-stable roommates problem, with Tamás Fleiner and Rob Irving.  In Proceedings of Match-UP: Matching Under Preferences – Algorithms and Complexity, held at ICALP 2008, pages 126-132.
  4. Popular matchings in the weighted capacitated house allocation problem, with Colin Sng.  In Proceedings of ACiD 2007: the 3rd Algorithms and Complexity in Durham workshop, volume 9 of Texts in Algorithmics, pages 129-140, College Publications, 2007.  The full version of this paper is available as Technical Report no. TR-2007-254, Department of Computing Science, University of Glasgow, 2007.
  5. Stable marriage with ties and bounded length preference lists, with Rob Irving and Gregg O’Malley.  In Proceedings of ACiD 2006: the 2nd Algorithms and Complexity in Durham workshop, volume 7 of Texts in Algorithmics, pages 95-106, College Publications, 2006.
  6. Vertex and edge covers with clustering properties: complexity and algorithms, with Henning Fernau.  In Proceedings of ACiD 2006: the 2nd Algorithms and Complexity in Durham workshop, volume 7 of Texts in Algorithmics, pages 69-84, College Publications, 2006.  The full version of this paper is available as Technical Report no. TR-2006-210, Department of Computing Science, University of Glasgow, 2006.
  7. The Kidney Exchange Game, with Katarína Cechlárová and Tamás Fleiner.  In Proceedings of SOR ’05: the 8th International Symposium on Operations Research in Slovenia, pages 77-83, 2005.  IM Preprint series A, no. 5/2005, PJ Šafárik University, Faculty of Science, Institute of Mathematics.
  8. A Constraint Programming Approach to the Hospitals / Residents Problem, with Gregg O’Malley, Patrick Prosser and Chris Unsworth.  In Proceedings of the Fourth Workshop on Modelling and Reformulating Constraint Satisfaction Problems, held at CP ’05, pages 28-43, 2005.  The full version of this paper is available as Technical Report no. TR-2005-196, Department of Computing Science, University of Glasgow, 2005.
  9. Modelling and solving the stable marriage problem using constraint programming, with Gregg O’Malley.  In Proceedings of the Fifth Workshop on Modelling and Solving Problems with Constraints, held at IJCAI ’05, pages 10-17, 2005.  The full version of this paper is available as Technical Report no. TR-2005-192, Department of Computing Science, University of Glasgow, 2005.
  10. Student-project allocation with preferences over projects, with Gregg O’Malley.  In Proceedings of ACiD 2005: the 1st Algorithms and Complexity in Durham workshop, volume 4 of Texts in Algorithmics, pages 69-80, KCL Publications, 2005.

In submission

  1. Pareto optimal matchings of students to courses in the presence of prerequisites, with Katarína Cechlárová and Bettina Klaus.
  2. Size versus truthfulness in the House Allocation problem (journal version), with Piotr Krysta, Baharak Rastegari and Jinshan Zhang.

Technical reports (not superseded by the above)

PhD thesis

Other papers