Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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
Identifiers
URN: urn:nbn:se:kth:diva-136802DOI: 10.1109/INFCOM.2010.5462027Scopus ID: 2-s2.0-77953309676ISBN: 978-1-4244-5836-3 (print)OAI: oai:DiVA.org:kth-136802DiVA: diva2:677221
Conference
29th IEEE Conference on Computer Communications 2010 (INFOCOM 2010)
Note

QC 20131211

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

Open Access in DiVA

fulltext(192 kB)72 downloads
File information
File name FULLTEXT01.pdfFile size 192 kBChecksum SHA-512
4363ea91fec87a81d267cd2e9be400040ebecc0363c10fcdda6d9fe32d8348f2b6015b1799d9f7c21021eb1e09218d1bfc17e8b1b833aaa9273acaccd596a5b8
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: 72 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: 65 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf