M.Sc Thesis
M.Sc Student Atsmonguz Liat Local Dynamic Weighted Matching Department of Electrical Engineering Professor Keidar Idit

Abstract

We define and solve the distributed dynamic weighted matching problem. Namely, unlike most previous work, we consider a scenario in which the network is asynchronous and dynamic, experiencing churn, failures, topology changes, and link weight changes. An algorithm that solves the dynamic weighted matching problem should adapt to such changes in the network and constantly output a matching.  We develop a new algorithm that solves this problem and guarantees a 2-approximation of the optimal solution. Moreover, we show that following local changes, the algorithm converges back to a 2-approximation after O(1) rounds.