Klientų aptarnavimas: +370 652 87781

Pagalba | Naujas vartotojas | Prisijungti

El. knyga: Algorithmics of Matching Under Preferences [World Scientific e-book]

David Manlove (Univ Of Glasgow, Uk)

Formatas: 524 pages
Serija: Series On Theoretical Computer Science 2
Išleidimo metai: 25-Apr-2013
Leidėjas: World Scientific Publishing Co Pte Ltd
ISBN-13: 9789814425254

Kitos knygos pagal šią temą:

Algorithms & data structures

World Scientific e-book
Kaina: 177,41 €*
* this price gives unlimited concurrent access for unlimited time

Formatas: 524 pages
Serija: Series On Theoretical Computer Science 2
Išleidimo metai: 25-Apr-2013
Leidėjas: World Scientific Publishing Co Pte Ltd
ISBN-13: 9789814425254

Kitos knygos pagal šią temą:

Algorithms & data structures

More info about World Scientific e-books

Partnerių interneto svetainė: http://www.worldscientific.com/worldscibooks/10.1142/8591#t=toc

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. The importance of the research area was recognised in 2012 through the award of the Nobel Prize in Economic Sciences to Alvin Roth and Lloyd Shapley.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.

Preface

vii

Foreword

xiii

Acknowledgments

List of Figures

xxvii

List of Tables

xxix

List of Algorithms

xxxi

1 Preliminary definitions, results and motivation

(48)

1.1 Introduction

(13)

1.1.1 Remit of this book

(3)

1.1.2 The matching problems under consideration

(3)

1.1.3 Existing literature on matching problems

(2)

1.1.4 Contribution of this book

(4)

1.1.5 Outline of this chapter

(1)

1.2 Matchings in graphs

(3)

1.3 The Hospitals / Residents problem (HR)

(14)

1.3.1 Introduction

(1)

1.3.2 Key definitions

(1)

1.3.3 Key results (up to 1989)

(3)

1.3.4 Stable Marriage problem (SM)

(4)

1.3.5 Hospitals / Residents problem with indifference

(3)

1.3.6 Other variants of HR

(1)

1.3.7 Motivation

(1)

1.4 The Stable Roommates problem (SR)

(7)

1.4.1 Introduction

(1)

1.4.2 Key definitions

(1)

1.4.3 Key results (up to 1989)

(1)

1.4.4 Rotations

(2)

1.4.5 Stable Roommates problem with indifference

(1)

1.4.6 Motivation

(1)

1.5 The House Allocation problem (HA) and its variants

(11)

1.5.1 Introduction

(1)

1.5.2 Formal definition of HA and HM

(2)

1.5.3 Pareto optimal matchings

(1)

1.5.4 Maximum utility matchings

(1)

1.5.5 Popular matchings

(1)

1.5.6 Profile-based optimal matchings

(3)

1.5.7 Extensions of HA

(1)

1.5.8 Motivation

(3)

Stable Matching Problems

(252)

2 The Stable Marriage problem: An update

(76)

2.1 Introduction

(3)

2.2 The 12 open problems of Gusfield and Irving

(11)

2.2.1 Introduction

(1)

2.2.2
1. Maximum number of stable matchings

(1)

2.2.3
2. The "divorce digraph"

(3)

2.2.4
3. Parallel algorithms for stable marriage

(1)

2.2.5
4. Batch stability testing

(1)

2.2.6
5. Structure of stable marriage with ties

(1)

2.2.7
6. Sex-equal matching

(2)

2.2.8
7. Lying and egalitarian matchings

(1)

2.2.9
10. Succinct certificates

(1)

2.2.10
11. Algorithmic improvements

(1)

2.3 The Subramanian and Feder papers

(7)

2.3.1 Subramanian: SRI and network stability

(3)

2.3.2 Feder: SRI and 2S AT

(2)

2.3.3 Other fixed-point approaches

(1)

2.4 Linear programming approaches

(1)

2.5 Constraint programming approaches

(6)

2.5.1 Introduction

(1)

2.5.2 Preliminaries

(1)

2.5.3 Overview of the CSP model

(1)

2.5.4 Arc consistency in the CSP model

(3)

2.6 Paths to stability

(11)

2.6.1 Introduction

(1)

2.6.2 The Roth-Vande Vate Mechanism

(6)

2.6.3 The Random Order Mechanism

(3)

2.6.4 Other decentralised algorithms

(2)

2.7 Median stable matchings

(9)

2.8 Size versus stability

(3)

2.9 Strategic issues

102

(5)

2.10 Further results

107

(18)

2.10.1 Stable Marriage problem with Forbidden pairs

107

(2)

2.10.2 Balanced stable matchings

109

(2)

2.10.3 Rationalizing matchings

111

(2)

2.10.4 Dinitz conjecture and stable marriage theory

113

(2)

2.10.5 The marriage graph

115

(2)

2.10.6 Sampling and counting

117

(2)

2.10.7 Online algorithms

119

(1)

2.10.8 Finding "good" stable matchings: unified approach

120

(2)

2.10.9 Locally stable matchings

122

(1)

2.10.10 Miscellaneous results

123

(2)

2.11 Conclusions and open problems

125

(2)

3 SM and HR with indifference

127

(46)

3.1 Introduction

127

(1)

3.2 Weak stability

128

(22)

3.2.1 Existence of a weakly stable matching

129

(1)

3.2.2 Absence of a lattice structure

130

(1)

3.2.3 Sizes of weakly stable matchings

130

(2)

3.2.4 NP-hardness of MAX SMTI

132

(3)

3.2.5 Parameterized complexity of MAX SMTI

135

(1)

3.2.6 Approximability of MAX SMTI and MAX HRT

136

(8)

3.2.7 Other problems involving weak stability

144

(6)

3.3 Strong stability

150

(9)

3.3.1 Existence of a strongly stable matching

150

(1)

3.3.2 Rural Hospitals Theorem for HRT

151

(1)

3.3.3 Strongly stable matchings form a lattice

152

(2)

3.3.4 Finding a strongly stable matching

154

(5)

3.4 Super-stability

159

(7)

3.4.1 Existence of a super-stable matching

159

(1)

3.4.2 Rural Hospitals Theorem for HRT

160

(1)

3.4.3 Super-stable matchings form a lattice

161

(2)

3.4.4 Finding a super-stable matching

163

(2)

3.4.5 Optimal super-stable matchings

165

(1)

3.5 Other results

166

(4)

3.5.1 Semi-strong stability

167

(1)

3.5.2 Many-many strongly stable matchings

168

(1)

3.5.3 Partially-ordered preference lists

168

(2)

3.6 Conclusions and open problems

170

(3)

4 The Stable Roommates problem

173

(52)

4.1 Introduction

173

(1)

4.2 Updates to open problems 8-12 from Gusfield and Irving

174

(7)

4.2.1 8: Solvable Roommates Instances

174

(2)

4.2.2 9: Roommates to Marriage

176

(1)

4.2.3 10: Succinct Certificates

177

(1)

4.2.4 11: Algorithmic Improvements

177

(2)

4.2.5 12: Optimal Roommates

179

(1)

4.2.6 12.1: Linear Programming for Roommates

180

(1)

4.3 Stable partitions

181

(13)

4.3.1 Introduction

181

(1)

4.3.2 Definition and structure of stable partitions

181

(3)

4.3.3 Algorithms for finding a stable partition

184

(4)

4.3.4 Maximum stable matchings

188

(2)

4.3.5 Stable half-matchings

190

(2)

4.3.6 P-stable matchings and absorbing sets

192

(2)

4.4 Mirror posets and median graphs

194

(5)

4.5 Indifference

199

(3)

4.5.1 Introduction

199

(1)

4.5.2 Weakly stable matchings

199

(2)

4.5.3 Strongly stable matchings

201

(1)

4.5.4 Super-stable matchings

201

(1)

4.6 "Almost stable" matchings

202

(7)

4.6.1 Introduction

202

(2)

4.6.2 Hardness results

204

(1)

4.6.3 Matchings with a constant no. of blocking pairs

205

(2)

4.6.4 Bounded length preference lists

207

(2)

4.6.5 Open problems

209

(1)

4.7 Globally-ranked pairs

209

(4)

4.7.1 Definitions and motivation for the SRTI-GRP model

209

(1)

4.7.2 Globally acyclic preferences

210

(1)

4.7.3 Weakly / strongly stable matchings in SRTI-GRP

210

(2)

4.7.4 Related work

212

(1)

4.8 Other extensions of SR

213

(10)

4.8.1 Introduction

213

(1)

4.8.2 Stable Roommates problem with Forbidden Pairs

213

(3)

4.8.3 Stable Crews problem

216

(1)

4.8.4 Stable Fixtures problem

216

(2)

4.8.5 Stable Multiple Activities problem

218

(1)

4.8.6 Stable Allocation problem

219

(1)

4.8.7 Stable Roommates problem with Choice Functions

220

(2)

4.8.8 Coalition Formation Games

222

(1)

4.9 Conclusions and open problems

223

(2)

5 Further stable matching problems

225

(76)

5.1 Introduction

225

(2)

5.2 HR with lower and common quotas

227

(16)

5.2.1 Introduction

227

(3)

5.2.2 HR with lower quotas (model 1)

230

(2)

5.2.3 HR with lower quotas (model 2)

232

(2)

5.2.4 HR with common quotas

234

(5)

5.2.5 Classified stable matching

239

(4)

5.3 HR with couples

243

(12)

5.3.1 Introduction

243

(1)

5.3.2 Problem definition and preliminary results

244

(3)

5.3.3 Algorithmic results

247

(4)

5.3.4 Consistent couples

251

(1)

5.3.5 Inseparable couples

252

(3)

5.4 Many-many stable matching

255

(5)

5.4.1 Introduction

255

(1)

5.4.2 Definition of the basic WF model

255

(1)

5.4.3 WF-1: preferences over individuals

256

(2)

5.4.4 WF-2: group preferences

258

(2)

5.5 The Student-Project Allocation Problem

260

(13)

5.5.1 Introduction

260

(1)

5.5.2 Lecturer preferences over students: SPA-S

261

(8)

5.5.3 Lecturer preferences over projects

269

(2)

5.5.4 Lecturer preferences over student-project pairs

271

(2)

5.6 3D stable matching problems

273

(14)

5.6.1 3D variants of SM

274

(7)

5.6.2 3D variants of SR

281

(6)

5.7 Exchange-stable matching problems

287

(6)

5.7.1 Exchange-stability as a solution concept

287

(2)

5.7.2 Exchange-blocking coalitions

289

(1)

5.7.3 Stable matchings that are exchange-stable

290

(3)

5.8 Two additional stable matching problems

293

(5)

5.8.1 Bistable matching problems

293

(3)

5.8.2 The Cycle Stable Roommates problem

296

(2)

5.9 Conclusions and open problems

298

(3)

El. knyga: Algorithmics of Matching Under Preferences [World Scientific e-book]

Paskyra ir nustatymai

Paieška

Ieškoti duomenų bazėje

Patikslinti paiešką

Temos Publishers Subjects

Pasirinkti pirkinių krepšelį