Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Constrained resource assignments: Fast algorithms and applications in wireless networks
KTH, School of Electrical Engineering (EES).
2016 (English)In: Management science, ISSN 0025-1909, E-ISSN 1526-5501, Vol. 62, no 7, p. 2070-2089Article in journal (Refereed) Published
Abstract [en]

Resource assignment problems occur in a vast variety of applications, from scheduling problems over image recognition to communication networks. Often these problems can be modeled by a maximum weight matching problem in (bipartite) graphs or generalizations thereof, and efficient and practical algorithms are known for these problems. Although in some of the applications an assignment of the resources may be needed only once, in many of these applications, the assignment has to be computed more often for different scenarios. In that case it is often essential that the assignments can be computed very fast. Moreover, implementing different assignments in different scenarios may come with a certain cost for the reconfiguration of the system. In this paper, we consider the problem of determining optimal assignments sequentially over a given time horizon, where consecutive assignments are coupled by constraints that control the cost of reconfiguration. We develop fast approximation and online algorithms for this problem with provable approximation guarantees and competitive ratios. Moreover, we present an extensive computational study about the applicability of our model and our algorithms in the context of orthogonal frequency division multiple access (OFDMA) wireless networks, finding a significant performance improvement for the total bandwidth of the system using our algorithms. For this application (the downlink of an OFDMA wireless cell) , the run time of matching algorithms is extremely important, having an acceptable range of a few milliseconds only. For the considered realistic instances, our algorithms perform extremely well: the solution quality is, on average, within a factor of 0.8-0.9 of optimal off-line solutions, and the running times are at most 5 ms per phase even in the worst case. Thus, our algorithms are well suited to be applied in the context of OFDMA systems.

Place, publisher, year, edition, pages
Institute for Operations Research and the Management Sciences (INFORMS), 2016. Vol. 62, no 7, p. 2070-2089
Keywords [en]
Analysis of algorithms, Approximation algorithms, Enabling technologies, Frequency allocation, Information systems, Matchings, Mobile networks, Algorithms, Combinatorial optimization, Image matching, Image recognition, Mobile telecommunication systems, Orthogonal frequency division multiplexing, Reconfigurable hardware, Wireless networks, Computational studies, Constrained resources, Maximum weight matching, Orthogonal frequency division multiple access, Resource assignment, Frequency division multiple access
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-197197DOI: 10.1287/mnsc.2015.2221ISI: 000379497100015Scopus ID: 2-s2.0-84978805723OAI: oai:DiVA.org:kth-197197DiVA, id: diva2:1055431
Note

QC 20161212

Available from: 2016-12-12 Created: 2016-11-30 Last updated: 2019-02-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus
By organisation
School of Electrical Engineering (EES)
In the same journal
Management science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 28 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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