Details of Grant 

EPSRC Reference:	GR/R84597/01
Title:	Algorithmics of Stable Matching Problems with Indifference
Principal Investigator:	Manlove, Professor D
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	School of Computing Science
Organisation:	University of Glasgow
Scheme:	Fast Stream
Starts:	01 October 2002	Ends:	31 March 2006	Value (£):	63,480
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:
Related Grants:
Panel History:
Summary on Grant Application Form
Stable matching problems are motivated in practice by large-scale applications such as centralised matching schemes, which assign agents together based on their preference lists. In Scotland, the USA and Canada for example, automated matching schemes annually construct stable matchings of graduating medical students to hospital posts, taking as input the preferences of students over hospitals and vice versa. Given the large numbers of participants typically involved, it is of paramount importance to employ efficient algorithms in such applications. In the case that all preference lists are strictly ordered, the underlying structure is well-understood, and this has led to the development of a range of efficient algorithms for these stable matching problems. However in practice the preference lists need not be totally ordered - hospitals may be indifferent among certain students, for example. This generalisation has not been widely studied from an algorithmic point of view, despite the important practical applications. The proposed project aims to explore in detail the algorithmic behaviour of stable matching problems with indifference - this will involve theoretical research, with the intended outcomes being new, efficient algorithms and complexity results, and also practical investigation, in the form of the empirical analysis of algorithm implementations.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.gla.ac.uk