### Skapa referens, olika format (klipp och klistra)

**Harvard**

Bhattacharya, S., Hoefer, M., Huang, C., Kavitha, T. och Wagner, L. (2015) *Maintaining Near-Popular Matchings*. Berlin : Springer Verlag

** BibTeX **

@conference{

Bhattacharya2015,

author={Bhattacharya, S. and Hoefer, M. and Huang, Chien-Chung and Kavitha, T. and Wagner, L.},

title={Maintaining Near-Popular Matchings},

booktitle={Automata, Languages, and Programming, Pt Ii},

isbn={978-3-662-47666-6},

pages={504-515},

abstract={We study dynamic matching problems in graphs among agents with preferences. Agents and/or edges of the graph arrive and depart iteratively over time. The goal is to maintain matchings that are favorable to the agent population and stable over time. More formally, we strive to keep a small unpopularity factor by making only a small amortized number of changes to the matching per round. Our main result is an algorithm to maintain matchings with unpopularity factor (Delta + k) by making an amortized number of O(Delta + Delta(2) /k) changes per round, for any k > 0. Here Delta denotes the maximum degree of any agent in any round. We complement this result by a variety of lower bounds indicating that matchings with smaller factor do not exist or cannot be maintained using our algorithm. As a byproduct, we obtain several additional results that might be of independent interest. First, our algorithm implies existence of matchings with small unpopularity factors in graphs with bounded degree. Second, given any matching M and any value alpha >= 1, we provide an efficient algorithm to compute a matching M' with unpopularity factor a over M if it exists. Finally, our results show the absence of voting paths in two-sided instances, even if we restrict to sequences of matchings with larger unpopularity factors (below Delta).},

publisher={Springer Verlag},

place={Berlin},

year={2015},

keywords={random-paths, preferences, stability },

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 227475

A1 Bhattacharya, S.

A1 Hoefer, M.

A1 Huang, Chien-Chung

A1 Kavitha, T.

A1 Wagner, L.

T1 Maintaining Near-Popular Matchings

YR 2015

T2 Automata, Languages, and Programming, Pt Ii

SN 978-3-662-47666-6

SP 504

OP 515

AB We study dynamic matching problems in graphs among agents with preferences. Agents and/or edges of the graph arrive and depart iteratively over time. The goal is to maintain matchings that are favorable to the agent population and stable over time. More formally, we strive to keep a small unpopularity factor by making only a small amortized number of changes to the matching per round. Our main result is an algorithm to maintain matchings with unpopularity factor (Delta + k) by making an amortized number of O(Delta + Delta(2) /k) changes per round, for any k > 0. Here Delta denotes the maximum degree of any agent in any round. We complement this result by a variety of lower bounds indicating that matchings with smaller factor do not exist or cannot be maintained using our algorithm. As a byproduct, we obtain several additional results that might be of independent interest. First, our algorithm implies existence of matchings with small unpopularity factors in graphs with bounded degree. Second, given any matching M and any value alpha >= 1, we provide an efficient algorithm to compute a matching M' with unpopularity factor a over M if it exists. Finally, our results show the absence of voting paths in two-sided instances, even if we restrict to sequences of matchings with larger unpopularity factors (below Delta).

PB Springer Verlag

LA eng

DO 10.1007/978-3-662-47666-6_40

LK http://dx.doi.org/10.1007/978-3-662-47666-6_40

OL 30