Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
type: Item
instance of: scholarly article
title: Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
zbMATH Open document ID: 1461.68153
author: Giorgos Georgiadis
author: Marina Papatriantafilou
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: A key property of overlay networks is the overlay nodes' ability to establish connections (or be matched) to other nodes by preference, based on some suitability metric related to, e.g., the node's distance, interests, recommendations, transaction history or available resources. When there are no preference cycles among the nodes, a stable matching exists in which nodes have maximized individual satisfaction, due to their choices, however no such guarantees are currently being given in the generic case. In this work, we employ the notion of node satisfaction to suggest a novel modeling for matching problems, suitable for overlay networks. We start by presenting a simple, yet powerful, distributed algorithm that solves the many-to-many matching problem with preferences. It achieves that by using local information and aggregate satisfaction as an optimization metric, while providing a guaranteed convergence and approximation ratio. Subsequently, we show how to extend the algorithm in order to support and adapt to changes in the nodes' connectivity and preferences. In addition, we provide a detailed experimental study that focuses on the levels of achieved satisfaction, as well as convergence and reconvergence speed.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7042190
zbMATH Keywords: matching
zbMATH Keywords: overlay networks
zbMATH Keywords: distributed algorithms
zbMATH Keywords: adaptive algorithms
Wikidata QID: Q57583912
describes a project that uses: PeerSim
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6040824
OpenAlex ID: W2005066278
cites work: Q4938640
cites work: Hard variants of stable marriage.
cites work: NP-complete stable matching problems
cites work: The stable fixtures problem -- a many-to-many extension of stable roommates
cites work: On a generalization of the stable roommates problem
cites work: Q4251057
cites work: A distributed polylogarithmic time algorithm for self-stabilizing skip graphs
cites work: Towards a scalable and robust DHT
cites work: Q3995616
cites work: The price of being near-sighted
cites work: Emergence of Scaling in Random Networks
cites work: Q3682518
cites work: Matching theory
cites work: Paths, Trees, and Flowers
cites work: College Admissions and the Stability of Marriage
cites work: Distributed approximate matching
cites work: Distributed Weighted Matching
cites work: Improved Distributed Approximate Matching
cites work: Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
DBLP publication ID: journals/algorithms/GeorgiadisP13
DOI: 10.3390/A6040824
description: scientific article; zbMATH DE number 7042190