License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.8
URN: urn:nbn:de:0030-drops-89439
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8943/
Go to the corresponding LIPIcs Volume Portal

Cooper, Frances ; Manlove, David

A 3/2-Approximation Algorithm for the Student-Project Allocation Problem

pdf-format:
LIPIcs-SEA-2018-8.pdf (0.5 MB)

Abstract

The Student-Project Allocation problem with lecturer preferences over Students (SPA-S) comprises three sets of agents, namely students, projects and lecturers, where students have preferences over projects and lecturers have preferences over students. In this scenario we seek a stable matching, that is, an assignment of students to projects such that there is no student and lecturer who have an incentive to deviate from their assignee/s. We study SPA-ST, the extension of SPA-S in which the preference lists of students and lecturers need not be strictly ordered, and may contain ties. In this scenario, stable matchings may be of different sizes, and it is known that MAX SPA-ST, the problem of finding a maximum stable matching in SPA-ST, is NP-hard. We present a linear-time 3/2-approximation algorithm for MAX SPA-ST and an Integer Programming (IP) model to solve MAX SPA-ST optimally. We compare the approximation algorithm with the IP model experimentally using randomly-generated data. We find that the performance of the approximation algorithm easily surpassed the 3/2 bound, constructing a stable matching within 92% of optimal in all cases, with the percentage being far higher for many instances.

BibTeX - Entry

@InProceedings{cooper_et_al:LIPIcs:2018:8943,
  author =	{Frances Cooper and David Manlove},
  title =	{{A 3/2-Approximation Algorithm for the Student-Project Allocation Problem}},
  booktitle =	{17th International Symposium on Experimental Algorithms  (SEA 2018)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8943},
  URN =		{urn:nbn:de:0030-drops-89439},
  doi =		{10.4230/LIPIcs.SEA.2018.8},
  annote =	{Keywords: Matching problems, Approximation, Algorithms, Stability}
}

Keywords: Matching problems, Approximation, Algorithms, Stability
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI