CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Overlays with preferences: Approximation algorithms for matching with preference lists

Giorgos Georgiadis (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers)) ; Marina Papatriantafilou (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers))
Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010) (1530-2075). (2010)
[Konferensbidrag, refereegranskat]

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.



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2010-01-12. Senast ändrad 2011-01-12.
CPL Pubid: 106815