Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Constrained Resource Assignments: Fast Approximations and Applications in Wireless Networks
Maastricht University.
Maastricht University.
KTH, Skolan för elektro- och systemteknik (EES), Kommunikationsteori.ORCID-id: 0000-0001-6682-6559
RWTH Aachen University.
2015 (Engelska)Ingår i: Management science, ISSN 0025-1909, E-ISSN 1526-5501Artikel i tidskrift (Övrigt vetenskapligt) Epub ahead of print
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.

Ort, förlag, år, upplaga, sidor
INFORMS , 2015.
Nationell ämneskategori
Telekommunikation
Identifikatorer
URN: urn:nbn:se:kth:diva-165933OAI: oai:DiVA.org:kth-165933DiVA, id: diva2:809161
Forskningsfinansiär
ICT - The Next Generation
Anmärkning

QC 20150531

Tillgänglig från: 2015-04-30 Skapad: 2015-04-30 Senast uppdaterad: 2017-12-04Bibliografiskt granskad

Open Access i DiVA

fulltext(538 kB)74 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 538 kBChecksumma SHA-512
7eb5c1fe2ab0259216eb88c99db5ec4d633878c5f4e615674302954ee55e203b5cda8540624ae11f9ac5fe5fae52929a68715793bdda022ce879aad55272bf5a
Typ fulltextMimetyp application/pdf

Personposter BETA

Gross, James

Sök vidare i DiVA

Av författaren/redaktören
Gross, James
Av organisationen
Kommunikationsteori
I samma tidskrift
Management science
Telekommunikation

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 74 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 617 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf