<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>7756</REFNUM><AUTHORS><AUTHOR>Abraham,D.J.</AUTHOR><AUTHOR>Cechlarova,K.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>Mehlhorn,K.</AUTHOR></AUTHORS><YEAR>2004</YEAR><TITLE>Pareto optimality in house allocation problems</TITLE><PLACE_PUBLISHED>Proceedings of ISAAC 2004: The 15th Annual International Symposium on Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science</PLACE_PUBLISHED><PUBLISHER>Springer Verlag</PUBLISHER><PAGES>3-15</PAGES><LABEL>Abraham:2004:7756</LABEL><ABSTRACT>We study Pareto optimal matchings in the context of house allocation problems. We present an O(\sqrt{n}m) algorithm, based on Gale’s Top Trading Cycles Method, for finding a maximum cardinality Pareto optimal matching, where n is the number of agents and m is the total length of the preference lists. By contrast, we show that the problem of finding a minimum cardinality Pareto optimal matching is NP-hard, though approximable within a factor of 2. We then show that there exist Pareto optimal matchings of all sizes between a minimum and maximum cardinality Pareto optimal matching. Finally, we introduce the concept of a signature, which allows us to give a characterization, checkable in linear time, of instances that admit a unique Pareto optimal matching.</ABSTRACT><NOTES>(c) Springer-Verlag <p></NOTES><URL>http://springerlink.metapress.com/content/b33l6cl34pb7b29e/?p=b9366264cd31412082dbdb1b1f1a16c6&pi=2</URL></RECORD></RECORDS></XML>