<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>9399</REFNUM><AUTHORS><AUTHOR>Kwanashie,A.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>2013</YEAR><TITLE>The Hospitals / Residents problem with Free Pairs</TITLE><PLACE_PUBLISHED>SoCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><PAGES>1-19</PAGES><ISBN>TR-2013-340</ISBN><LABEL>Kwanashie:2013:9399</LABEL><KEYWORDS><KEYWORD>Locally stable matching; NP-hard problem; Approximation algorithm; Admissible pair; Free pair</KEYWORD></KEYWORDS<ABSTRACT>In the classical Hospitals/Residents problem, a stable matching M is sought which ensures that no blocking pair can exist in which a resident r and hospital h can improve relative to M by becoming assigned to each other. Such a situation is undesirable as it could naturally lead to r and h forming a private arrangement outside of the matching. This however assumes that a blocking pair that exists in theory would invariably lead to a matching being undermined in practice. However such a situation need not arise if the lack of social ties between agents prevents an awareness of certain blocking pairs in practice. Relaxing the stability definition to take such a scenario into account can yield larger stable matchings.<p> In this paper, we define the Hospitals/Residents problem with Free Pairs (HRF) in which a subset of acceptable resident-hospital pairs are defined as free. This means that they can belong to a matching M but they can never block M. Free pairs correspond to resident and hospitals that do not know one another. Relative to a relaxed stability definition for HRF, called local stability, we show that locally stable matchings can have different sizes and the problem of finding a maximum locally stable matching is NP- hard, though approximable within 3/2. Furthermore we give polynomial time algorithms for two special cases of the problem</ABSTRACT></RECORD></RECORDS></XML>