Improving Distributed Maximum Weighted Matchings for Communication Networks

Basit Öğe Kaydı
dc.contributor.authorIleri, Can Umut
dc.contributor.authorDagdeviren, Orhan
dc.date.accessioned2019-10-27T11:18:44Z
dc.date.available2019-10-27T11:18:44Z
dc.date.issued2017
dc.departmentEge Üniversitesien_US
dc.description5th IEEE International Black Sea Conference on Communications and Networking (IEEE BlackSeaCom) -- JUN 05-08, 2017 -- Istanbul, TURKEYen_US
dc.description.abstractMatching 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%.en_US
dc.description.sponsorshipIEEEen_US
dc.description.sponsorshipTUBITAKTurkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK) [215E115, BIDEB-1001]en_US
dc.description.sponsorshipAuthors would like to thank TUBITAK for the project grant (215E115) and the PhD research grant (BIDEB-1001).en_US
dc.identifier.endpage268en_US
dc.identifier.isbn978-1-5090-5049-9
dc.identifier.issn2375-8236
dc.identifier.issn2375-8236en_US
dc.identifier.scopusqualityN/Aen_US
dc.identifier.startpage264en_US
dc.identifier.urihttps://hdl.handle.net/11454/32610
dc.identifier.wosWOS:000427892400053en_US
dc.identifier.wosqualityN/Aen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.language.isoenen_US
dc.publisherIeeeen_US
dc.relation.ispartof2017 Ieee International Black Sea Conference on Communications and Networking (Blackseacom)en_US
dc.relation.ispartofseriesInternational Black Sea Conference on Communications and Networking
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectWeighted matchingen_US
dc.subjectcommunication networksen_US
dc.subjectdistributed algorithmsen_US
dc.subjectapproximation algorithmsen_US
dc.titleImproving Distributed Maximum Weighted Matchings for Communication Networksen_US
dc.typeConference Objecten_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu