cover

The book has now been published (ISBN 978-981-4425-24-7). The print edition is available to buy from the publisher or via Amazon.co.uk or Amazon.com. The e-edition (ISBN 978-981-4425-25-4)and Kindle edition (ISBN 978-981-4425-26-1) are also available to purchase and some sample material is available to view for free.

Detailed Table of 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

Part 1: Stable Matching Problems

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 Open problems

3. The Stable Marriage and Hospitals / Residents
problems 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

Errata

Publisher’s flyer

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 Concluding remarks

Part 2: Other Optimal Matching 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 Concluding remarks

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 Concluding remarks

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