Change search
ReferencesLink to record
Permanent link

Direct link
The k–Constrained Bipartite Matching Problem: Approximation Algorithms and Applications to Wireless Networks
RWTH Aachen University, Germany.ORCID iD: 0000-0001-6682-6559
2010 (English)In: Proceedings IEEE INFOCOM, 2010, IEEE conference proceedings, 2010, 1-9 p.Conference paper (Refereed)
Abstract [en]

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.
National Category
Communication Systems Telecommunications
URN: urn:nbn:se:kth:diva-136802DOI: 10.1109/INFCOM.2010.5462027ScopusID: 2-s2.0-77953309676ISBN: 978-1-4244-5836-3OAI: diva2:677221
29th IEEE Conference on Computer Communications 2010 (INFOCOM 2010)

QC 20131211

Available from: 2013-12-09 Created: 2013-12-09 Last updated: 2013-12-11Bibliographically approved

Open Access in DiVA

fulltext(192 kB)50 downloads
File information
File name FULLTEXT01.pdfFile size 192 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusIEEEXplore

Search in DiVA

By author/editor
Gross, James
Communication SystemsTelecommunications

Search outside of DiVA

GoogleGoogle Scholar
Total: 50 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 46 hits
ReferencesLink to record
Permanent link

Direct link