Coverart for item
The Resource Algorithmics of matching under preferences, by David Manlove ; with a foreword by Kurt Mehlhorn

Algorithmics of matching under preferences, by David Manlove ; with a foreword by Kurt Mehlhorn

Label
Algorithmics of matching under preferences
Title
Algorithmics of matching under preferences
Statement of responsibility
by David Manlove ; with a foreword by Kurt Mehlhorn
Creator
Contributor
Subject
Language
eng
Summary
Matching 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 update to The Stable Marriage Problem: Structure and Algorithms (D Gusfield and R W Irving, MIT Press, 1989) in connection with stable matching problems, whilst also broadening the scope to include matching problems with preferences under a range of alternative optimality criteria.--
Member of
Assigning source
Provided by Publisher
http://bibfra.me/vocab/relation/authorofintroduction
ihPqbWQmT8Y
Cataloging source
UKMGB
http://library.link/vocab/creatorName
Manlove, David F
Index
index present
Literary form
non fiction
Nature of contents
bibliography
http://library.link/vocab/relatedWorkOrContributorDate
1949-
http://library.link/vocab/relatedWorkOrContributorName
Mehlhorn, Kurt
Series statement
Series on theoretical computer science
Series volume
vol. 2
http://library.link/vocab/subjectName
Matching theory
Label
Algorithmics of matching under preferences, by David Manlove ; with a foreword by Kurt Mehlhorn
Instantiates
Publication
Copyright
Bibliography note
Includes bibliographical references (pages 417-460) and index
Carrier category
volume
Carrier category code
nc
Carrier MARC source
rdacarrier.
Content category
text
Content type code
txt
Content type MARC source
rdacontent.
Contents
1. Preliminary definitions, results and motivation. 1.1. Introduction. 1.2. Matchings in graphs. 1.3. The Hospitals / Residents problem (HR). 1.4. The Stable Roommates problem (SR). 1.5. The House Allocation problem (HA) and its variants -- 2. The Stable Marriage problem: an update. 2.1. Introduction. 2.2. The 12 open problems of Gusfield and Irving. 2.3. The Subramanian and Feder papers. 2.4. Linear programming approaches. 2.5. Constraint programming approaches. 2.6. Paths to stability. 2.7. Median stable matchings. 2.8. Size versus stability. 2.9. Strategic issues. 2.10. Further results. 2.11. Conclusions and open problems -- 3. SM and HR with indifference. 3.1. Introduction. 3.2. Weak stability. 3.3. Strong stability. 3.4. Super-stability. 3.5. Other results. 3.6. Conclusions and open problems -- 4. The Stable Roommates problem. 4.1. Introduction. 4.2. Updates to open problems 8-12 from Gusfield & Irving. 4.3. Stable partitions. 4.4. Mirror posets and median graphs. 4.5. Indifference. 4.6. "Almost stable" matchings. 4.7. Globally-ranked pairs. 4.8. Other extensions of SR. 4.9. Conclusions and open problems -- 5. Further stable matching problems. 5.1. Introduction. 5.2. HR with lower and common quotas. 5.3. HR with couples. 5.4. Many-many stable matching. 5.5. The Student-Project Allocation Problem. 5.6. 3D stable matching problems. 5.7. Exchange-stable matching problems. 5.8. Two additional stable matching problems. 5.9. Conclusions and open problems -- 6. Pareto optimal matchings. 6.1. Introduction. 6.2. House Allocation problem. 6.3. Capacitated House Allocation problem. 6.4. Hospitals / Residents problem. 6.5. Stable Roommates problem. 6.6. Conclusions and open problems -- 7. Popular matchings. 7.1. Introduction. 7.2. House Allocation problem. 7.3. Capacitated House Allocation problem. 7.4. Weighted House Allocation problem. 7.5. Stable Roommates problem. 7.6. Stable Marriage problem. 7.7. Conclusions and open problems -- 8. Profile-based optimal matchings. 8.1. Introduction. 8.2. Rank-maximal matchings. 8.3. Greedy and generous maximum matchings. 8.4. Weight-maximal matchings. 8.5. Other profile-based optimal matching problems. 8.6. Conclusions and open problems
Control code
FIEb17603791
Dimensions
24 cm.
Extent
xxxi, 491 pages
Isbn
9789814425247
Media category
unmediated
Media MARC source
rdamedia.
Media type code
n
System control number
(OCoLC)826660079
Label
Algorithmics of matching under preferences, by David Manlove ; with a foreword by Kurt Mehlhorn
Publication
Copyright
Bibliography note
Includes bibliographical references (pages 417-460) and index
Carrier category
volume
Carrier category code
nc
Carrier MARC source
rdacarrier.
Content category
text
Content type code
txt
Content type MARC source
rdacontent.
Contents
1. Preliminary definitions, results and motivation. 1.1. Introduction. 1.2. Matchings in graphs. 1.3. The Hospitals / Residents problem (HR). 1.4. The Stable Roommates problem (SR). 1.5. The House Allocation problem (HA) and its variants -- 2. The Stable Marriage problem: an update. 2.1. Introduction. 2.2. The 12 open problems of Gusfield and Irving. 2.3. The Subramanian and Feder papers. 2.4. Linear programming approaches. 2.5. Constraint programming approaches. 2.6. Paths to stability. 2.7. Median stable matchings. 2.8. Size versus stability. 2.9. Strategic issues. 2.10. Further results. 2.11. Conclusions and open problems -- 3. SM and HR with indifference. 3.1. Introduction. 3.2. Weak stability. 3.3. Strong stability. 3.4. Super-stability. 3.5. Other results. 3.6. Conclusions and open problems -- 4. The Stable Roommates problem. 4.1. Introduction. 4.2. Updates to open problems 8-12 from Gusfield & Irving. 4.3. Stable partitions. 4.4. Mirror posets and median graphs. 4.5. Indifference. 4.6. "Almost stable" matchings. 4.7. Globally-ranked pairs. 4.8. Other extensions of SR. 4.9. Conclusions and open problems -- 5. Further stable matching problems. 5.1. Introduction. 5.2. HR with lower and common quotas. 5.3. HR with couples. 5.4. Many-many stable matching. 5.5. The Student-Project Allocation Problem. 5.6. 3D stable matching problems. 5.7. Exchange-stable matching problems. 5.8. Two additional stable matching problems. 5.9. Conclusions and open problems -- 6. Pareto optimal matchings. 6.1. Introduction. 6.2. House Allocation problem. 6.3. Capacitated House Allocation problem. 6.4. Hospitals / Residents problem. 6.5. Stable Roommates problem. 6.6. Conclusions and open problems -- 7. Popular matchings. 7.1. Introduction. 7.2. House Allocation problem. 7.3. Capacitated House Allocation problem. 7.4. Weighted House Allocation problem. 7.5. Stable Roommates problem. 7.6. Stable Marriage problem. 7.7. Conclusions and open problems -- 8. Profile-based optimal matchings. 8.1. Introduction. 8.2. Rank-maximal matchings. 8.3. Greedy and generous maximum matchings. 8.4. Weight-maximal matchings. 8.5. Other profile-based optimal matching problems. 8.6. Conclusions and open problems
Control code
FIEb17603791
Dimensions
24 cm.
Extent
xxxi, 491 pages
Isbn
9789814425247
Media category
unmediated
Media MARC source
rdamedia.
Media type code
n
System control number
(OCoLC)826660079

Library Locations

    • Badia FiesolanaBorrow it
      Via dei Roccettini 9, San Domenico di Fiesole, 50014, IT
      43.803074 11.283055
Processing Feedback ...