The k–Constrained Bipartite Matching Problem: Approximation Algorithms and Applications to Wireless Networks
2010 (English)In: Proceedings IEEE INFOCOM, 2010, IEEE conference proceedings, 2010, 1-9 p.Conference paper (Refereed)
In communication networks, resource assignment problems appear in several different settings. These problems are often modeled by a maximum weight matching problem in bipartite graphs and efficient matching algorithms are well known. In several applications, the corresponding matching problem has to be solved many times in a row as the underlying system operates in a time-slotted fashion and the edge weights change over time. However, changing the assignments can come with a certain cost for reconfiguration that depends on the number of changed edges between subsequent assignments. In order to control the cost of reconfiguration, we propose the k-constrained bipartite matching problem for bipartite graphs, which seeks an optimal matching that realizes at most k changes from a previous matching. We provide fast approximation algorithms with provable guarantees for this problem. Furthermore, to cope with the sequential nature of assignment problems, we introduce an online variant of the k-constrained matching problem and derive online algorithms that are based on our approximation algorithms for the k-constrained bipartite matching problem. Finally, we establish the applicability of our model and our algorithms in the context of OFDMA wireless networks finding a significant performance improvement for the proposed algorithms.
Place, publisher, year, edition, pages
IEEE conference proceedings, 2010. 1-9 p.
Communication Systems Telecommunications
IdentifiersURN: urn:nbn:se:kth:diva-136802DOI: 10.1109/INFCOM.2010.5462027ScopusID: 2-s2.0-77953309676ISBN: 978-1-4244-5836-3OAI: oai:DiVA.org:kth-136802DiVA: diva2:677221
29th IEEE Conference on Computer Communications 2010 (INFOCOM 2010)
QC 201312112013-12-092013-12-092013-12-11Bibliographically approved