Improving distributed maximum weighted matchings for communication networks

Can Umut Ileri, Orhan Dagdeviren

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

Matching problem has been attracting a growing attention in network design, especially in wireless communication networks. Although there is an exact polynomial-time sequential algorithm for the weighted version of the problem, all the related distributed algorithms are approximation algorithms. In this paper we present a distributed heuristic which improves the weight of a given matching in time proportional to the number of nodes. Our algorithm assumes the asynchronous communication model in which the message size is limited to O (log n) bits. To the best of our knowledge, it is the first distributed weighted matching algorithm which benefits from augmentation of alternating paths having size larger than 3 and uses small messages. We also provide results of our simulations on random geometric graphs. Computational results show that our algorithm improves the approximated solutions of other weighted matching algorithms roughly by 1-3% and closes the gap between the approximation ratio and the optimum solution by 9-26%.

Original languageEnglish
Title of host publication2017 IEEE International Black Sea Conference on Communications and Networking, BlackSeaCom 2017
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1-5
Number of pages5
Volume2018-January
ISBN (Electronic)9781509050499
DOIs
Publication statusPublished - 31 Jan 2018
Externally publishedYes
Event2017 IEEE International Black Sea Conference on Communications and Networking, BlackSeaCom 2017 - Istanbul, Turkey
Duration: 5 Jun 20178 Jun 2017

Conference

Conference2017 IEEE International Black Sea Conference on Communications and Networking, BlackSeaCom 2017
CountryTurkey
CityIstanbul
Period5/06/178/06/17

Keywords

  • approximation algorithms
  • communication networks
  • distributed algorithms
  • Weighted matching

Fingerprint Dive into the research topics of 'Improving distributed maximum weighted matchings for communication networks'. Together they form a unique fingerprint.

Cite this