05402nam 2200649 a 450 991045233420332120200520144314.01-299-46251-0981-4425-25-7(CKB)2550000001019240(EBL)1168176(OCoLC)840497867(SSID)ssj0000906097(PQKBManifestationID)11506366(PQKBTitleCode)TC0000906097(PQKBWorkID)10945451(PQKB)11127301(MiAaPQ)EBC1168176(WSP)00002975(Au-PeEL)EBL1168176(CaPaEBR)ebr10691894(CaONFJC)MIL477501(EXLCZ)99255000000101924020130514d2013 uy 0engur|n|---|||||txtccrAlgorithmics of matching under preferences[electronic resource] /David F. Manlove ; with a foreword by Kurt Mehlhorn[Hackensack] N.J. World Scientificc20131 online resource (524 p.)Series on theoretical computer science,1793-849X ;v. 2Description based upon print version of record.981-4425-24-9 Includes bibliographical references and index.Preface; Foreword; Acknowledgments; Contents; List of Figures; List of Tables; List of Algorithms; 1. Preliminary definitions, results and motivation; 1.1 Introduction; 1.1.1 Remit of this book; 1.1.1.1 Matching under preferences; 1.1.1.2 Free-for-all markets; 1.1.1.3 Centralised matching schemes; 1.1.2 The matching problems under consideration; 1.1.2.1 Classification of matching problems; 1.1.2.2 Bipartite matching problems with two-sided preferences; 1.1.2.3 Bipartite matching problems with one-sided preferences; 1.1.2.4 Non-bipartite matching problems with preferences1.1.2.5 Further problem variants1.1.3 Existing literature on matching problems; 1.1.3.1 Algorithms and complexity literature; 1.1.3.2 Game theory and economics literature; 1.1.3.3 Algorithmic mechanism design literature; 1.1.4 Contribution of this book; 1.1.4.1 General overview; 1.1.4.2 Chapter outline; 1.1.4.3 What the book does not contribute; 1.1.5 Outline of this chapter; 1.2 Matchings in graphs; 1.3 The Hospitals / Residents problem (hr); 1.3.1 Introduction; 1.3.2 Key definitions; 1.3.3 Key results (up to 1989); 1.3.4 Stable Marriage problem (sm); 1.3.4.1 Key definitions1.3.4.2 Key results (up to 1989)1.3.4.3 Rotations; 1.3.5 Hospitals / Residents problem with indifference; 1.3.6 Other variants of hr; 1.3.6.1 Couples; 1.3.6.2 Many-many stable matchings; 1.3.6.3 Master lists; 1.3.7 Motivation; 1.4 The Stable Roommates problem (sr); 1.4.1 Introduction; 1.4.2 Key definitions; 1.4.3 Key results (up to 1989); 1.4.4 Rotations; 1.4.5 Stable Roommates problem with indifference; 1.4.6 Motivation; 1.5 The House Allocation problem (ha) and its variants; 1.5.1 Introduction; 1.5.2 Formal definition of ha and hm; 1.5.3 Pareto optimal matchings1.5.4 Maximum utility matchings1.5.5 Popular matchings; 1.5.6 Profile-based optimal matchings; 1.5.7 Extensions of ha; 1.5.8 Motivation; Stable Matching Problems; 2. The Stable Marriage problem: An update; 2.1 Introduction; 2.2 The 12 open problems of Gusfield and Irving; 2.2.1 Introduction; 2.2.2 1. Maximum number of stable matchings; 2.2.3 2. The "divorce digraph"; 2.2.4 3. Parallel algorithms for stable marriage; 2.2.5 4. Batch stability testing; 2.2.6 5. Structure of stable marriage with ties; 2.2.7 6. Sex-equal matching; 2.2.8 7. Lying and egalitarian matchings2.2.9 10. Succinct certificates2.2.10 11. Algorithmic improvements; 2.3 The Subramanian and Feder papers; 2.3.1 Subramanian: sri and network stability; 2.3.2 Feder: sri and 2-sat; 2.3.3 Other fixed-point approaches; 2.4 Linear programming approaches; 2.5 Constraint programming approaches; 2.5.1 Introduction; 2.5.2 Preliminaries; 2.5.3 Overview of the csp model; 2.5.4 Arc consistency in the csp model; 2.6 Paths to stability; 2.6.1 Introduction; 2.6.2 The Roth-Vande Vate Mechanism; 2.6.3 The Random Order Mechanism; 2.6.4 Other decentralised algorithms; 2.7 Median stable matchings2.8 Size versus stabilityMatching problems with preferences are all around us - they arise when agents seek to be allocated to one another on the basis of ranked preferences over potential outcomes. Efficient algorithms are needed for producing matchings that optimise the satisfaction of the agents according to their preference lists.In recent years there has been a sharp increase in the study of algorithmic aspects of matching problems with preferences, partly reflecting the growing number of applications of these problems worldwide. This book describes the most important results in this area, providing a timely updaSeries on theoretical computer science ;v. 2.Computer algorithmsElectronic books.Computer algorithms.005.1Manlove David F928616Mehlhorn Kurt746269MiAaPQMiAaPQMiAaPQBOOK9910452334203321Algorithmics of matching under preferences2087020UNINA