Cyclic stable matching for three-sided networking services

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

15 Scopus Citations
View graph of relations

Author(s)

  • Lin Cui
  • Weijia Jia

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)351-363
Journal / PublicationComputer Networks
Volume57
Issue number1
Publication statusPublished - 16 Jan 2013

Abstract

Three-sided relationship is very common in the social and economic area, e.g., the supplier-firm-buyer relationship, kidney exchange problem. The three-sided relationship can also be found in many scenarios of computer networking systems involving three types of agents, which we regard as three-sided networks. For example, in sensor networks, data are retrieved from data sources (sensors) and forwarded to users through a group of servers. In such three-sided networks, users always prefer to receive the best data services from data sources, data sources would choose servers that are more efficient to deliver their data, and servers try to satisfy more users. Such preferences form a specific cyclic relationship and how to optimally allocate network resources to satisfy preferences of all parties becomes a great challenge. In this paper, inspired by the three-sided stable matching, we model the Three-sided Matching with Size and Cyclic preference (TMSC) problem for data sources, servers and users, aiming to find a stable matching for them, where all their preferences are satisfied. TMSC is different from the traditional three-sided matching models, as each server may normally serve more than one users. We show that the problem of seeking an optimal stable matching with maximum cardinality is NP-hard and propose efficient algorithms for the restricted model of TMSC problem to find a stable matching. The effectiveness of the proposed algorithms is validated through extensive simulations.© 2012 Elsevier B.V. All rights reserved.© 2012 Elsevier B.V. All rights reserved.

Research Area(s)

  • Cyclic preference, Stability, Three-sided matching

Citation Format(s)

Cyclic stable matching for three-sided networking services. / Cui, Lin; Jia, Weijia.

In: Computer Networks, Vol. 57, No. 1, 16.01.2013, p. 351-363.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review