Improving distributed maximum weighted matchings for communication networks

2017 IEEE International Black Sea Conference on Communications and Networking, BlackSeaCom 2017 -- 5 June 2017 through 8 June 2017 -- -- 1345102-s2.0-85050716269Matching 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%. © 2017 IEEE.215E115, BIDEB-1001Authors would like to thank TUBITAK for the project grant (215E115) and the PhD research grant (BIDEB-1001)