Improving distributed maximum weighted matchings for communication networks
Bildiriler > Tam Metin Bildiri
Yazarlar: Can Umut Ileri, Orhan DAĞDEVİREN
2017 IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom), , , Uluslararası, Tam Metin Bildiri, cilt 2, ss 1-5
DOI: 10.1109/blackseacom.2017.8277709
Özet
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%.