The Library
Maintaining near-popular matchings
Tools
Bhattacharya, Sayan, Hoefer, Martin, Huang, Chien-Chung, Kavitha, Telikepalli and Wagner, Lisa (2015) Maintaining near-popular matchings. In: International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 6-10 Jul 2015. Published in: Automata, Languages, and Programming, 9135 pp. 504-515. ISBN 9783662476659. doi:10.1007/978-3-662-47666-6_40 ISSN 0302-9743.
|
PDF
WRAP-maintaining-near-popular-matchings-Bhattachaya-2015.pdf - Accepted Version - Requires a PDF viewer. Download (646Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-662-47666-6_40
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 (Δ+k)(Δ+k) by making an amortized number of O(Δ+Δ2/k)O(Δ+Δ2/k) changes per round, for any k>0k>0 . Here ΔΔ 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 α≥1α≥1 , we provide an efficient algorithm to compute a matching M′M′ with unpopularity factor αα 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 Δ)Δ)
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Graph theory | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Journal or Publication Title: | Automata, Languages, and Programming | ||||
Publisher: | Springer | ||||
Place of Publication: | Berlin, Heidelberg | ||||
ISBN: | 9783662476659 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Automata, Languages, and Programming | ||||
Editor: | Halldórsson , M. and Iwama , K. and Kobayashi , N. and Speckmann , B. | ||||
Official Date: | 2015 | ||||
Dates: |
|
||||
Volume: | 9135 | ||||
Page Range: | pp. 504-515 | ||||
DOI: | 10.1007/978-3-662-47666-6_40 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 26 September 2017 | ||||
Date of first compliant Open Access: | 26 September 2017 | ||||
Funder: | Deutsche Forschungsgemeinschaft (DFG) | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | International Colloquium on Automata, Languages, and Programming | ||||
Type of Event: | Other | ||||
Location of Event: | Kyoto, Japan | ||||
Date(s) of Event: | 6-10 Jul 2015 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year