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

**Harvard**

Georgiadis, G. och Papatriantafilou, M. (2010) *Overlays with preferences: Approximation algorithms for matching with preference lists*.

** BibTeX **

@conference{

Georgiadis2010,

author={Georgiadis, Giorgos and Papatriantafilou, Marina},

title={Overlays with preferences: Approximation algorithms for matching with preference lists},

booktitle={Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010)},

isbn={978-1-4244-6442-5},

abstract={A key property of overlay networks, that is going to play an
important part in future networking solutions, is the peers'
ability to establish connections with other peers based on some suitability metric related to e.g. the node's distance,
interests, recommendations, transaction history or available
resources. Each node may choose individually an appropriate
metric and try to connect or be matched with the available
peers that it considers best. When there are no preference
cycles among the peers, it has been proven that a stable
matching exists, where peers have maximized the individual
satisfaction gleaned of their choices. However, no such
guarantees are currently being given for the cases where cycles may exist and known methods may not be able to resolve ``oscillations'' in preference-based connectivity and reach stability. In this work we present a simple yet powerful distributed algorithm that uses aggregate satisfaction as an optimization metric. The algorithm is a generalization of a known elegant approximation one-to-one matching algorithm, into the many-to-many case. We prove that the total satisfaction achieved by our algorithm is a $\frac{1}{4}\left( {1 + \frac{1}{{{b_{\max }}}}} \right)$-approximation of the maximum total satisfaction in the network, where $b_{\max}$ is the maximum number of possible connections of a peer in the overlay.},

year={2010},

}

** RefWorks **

RT Conference Proceedings

SR Print

ID 106815

A1 Georgiadis, Giorgos

A1 Papatriantafilou, Marina

T1 Overlays with preferences: Approximation algorithms for matching with preference lists

YR 2010

T2 Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010)

SN 978-1-4244-6442-5

AB A key property of overlay networks, that is going to play an
important part in future networking solutions, is the peers'
ability to establish connections with other peers based on some suitability metric related to e.g. the node's distance,
interests, recommendations, transaction history or available
resources. Each node may choose individually an appropriate
metric and try to connect or be matched with the available
peers that it considers best. When there are no preference
cycles among the peers, it has been proven that a stable
matching exists, where peers have maximized the individual
satisfaction gleaned of their choices. However, no such
guarantees are currently being given for the cases where cycles may exist and known methods may not be able to resolve ``oscillations'' in preference-based connectivity and reach stability. In this work we present a simple yet powerful distributed algorithm that uses aggregate satisfaction as an optimization metric. The algorithm is a generalization of a known elegant approximation one-to-one matching algorithm, into the many-to-many case. We prove that the total satisfaction achieved by our algorithm is a $\frac{1}{4}\left( {1 + \frac{1}{{{b_{\max }}}}} \right)$-approximation of the maximum total satisfaction in the network, where $b_{\max}$ is the maximum number of possible connections of a peer in the overlay.

LA eng

OL 30