LEADER 05402nam 2200649 a 450 001 9910452334203321 005 20200520144314.0 010 $a1-299-46251-0 010 $a981-4425-25-7 035 $a(CKB)2550000001019240 035 $a(EBL)1168176 035 $a(OCoLC)840497867 035 $a(SSID)ssj0000906097 035 $a(PQKBManifestationID)11506366 035 $a(PQKBTitleCode)TC0000906097 035 $a(PQKBWorkID)10945451 035 $a(PQKB)11127301 035 $a(MiAaPQ)EBC1168176 035 $a(WSP)00002975 035 $a(Au-PeEL)EBL1168176 035 $a(CaPaEBR)ebr10691894 035 $a(CaONFJC)MIL477501 035 $a(EXLCZ)992550000001019240 100 $a20130514d2013 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithmics of matching under preferences$b[electronic resource] /$fDavid F. Manlove ; with a foreword by Kurt Mehlhorn 210 $a[Hackensack] N.J. $cWorld Scientific$dc2013 215 $a1 online resource (524 p.) 225 1 $aSeries on theoretical computer science,$x1793-849X ;$vv. 2 300 $aDescription based upon print version of record. 311 $a981-4425-24-9 320 $aIncludes bibliographical references and index. 327 $aPreface; 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 preferences 327 $a1.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 definitions 327 $a1.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 matchings 327 $a1.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 matchings 327 $a2.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 matchings 327 $a2.8 Size versus stability 330 $aMatching 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 upda 410 0$aSeries on theoretical computer science ;$vv. 2. 606 $aComputer algorithms 608 $aElectronic books. 615 0$aComputer algorithms. 676 $a005.1 700 $aManlove$b David F$0928616 701 $aMehlhorn$b Kurt$0746269 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910452334203321 996 $aAlgorithmics of matching under preferences$92087020 997 $aUNINA