LEADER 00649oam 2200205z- 450 001 996397222003316 005 20200818212645.0 035 $a(CKB)4940000000063256 035 $a(EEBO)2273415555 035 $a(OCoLC)9922663400971 035 $a(EXLCZ)994940000000063256 100 $a20191209c1507uuuu -u- - 101 0 $aeng 200 10$a[Lac puerorum M. Holti anglice mylke for children] 210 $aBelgium$cExaratum est pñs h⁰ opusculum per me Johannem de Doesborch 700 $aHolt$b John$0526613 906 $aBOOK 912 $a996397222003316 996 $aLac puerorum M. Holti anglice mylke for children$92386235 997 $aUNISA LEADER 05189oam 2200565 450 001 9910813941703321 005 20190911112728.0 010 $a1-299-46251-0 010 $a981-4425-25-7 035 $a(OCoLC)895087324 035 $a(MiFhGG)GVRL8RGB 035 $a(EXLCZ)992550000001019240 100 $a20130716h20132013 uy 0 101 0 $aeng 135 $aurun|---uuuua 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithmics of matching under preferences /$fDavid F. Manlove, University of Glasgow, UK ; with a foreword by Kurt Mehlhorn 210 $a[Hackensack] N.J. $cWorld Scientific$dc2013 210 1$aNew Jersey :$cWorld Scientific,$d[2013] 210 4$d?2013 215 $a1 online resource (xxxi, 491 pages) 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 $aMatching theory 606 $aMarriage theorem 606 $aComputer science$xMathematics 615 0$aMatching theory. 615 0$aMarriage theorem. 615 0$aComputer science$xMathematics. 676 $a005.1 700 $aManlove$b David F$01707965 702 $aMehlhorn$b Kurt$f1949- 801 0$bMiFhGG 801 1$bMiFhGG 906 $aBOOK 912 $a9910813941703321 996 $aAlgorithmics of matching under preferences$94096603 997 $aUNINA