Constrained Resource Assignments: Fast Algorithms and Applications in Wireless Networks

André Berger (), James Gross (), Tobias Harks () and Simon Tenbusch ()
Additional contact information
André Berger: Department of Quantitative Economics, Maastricht University, 6200 MD Maastricht, Netherlands
James Gross: School of Electrical Engineering, KTH Royal Institute of Technology, S100 44 Stockholm, Sweden
Tobias Harks: Institute of Mathematics, University of Augsburg, 86135 Augsburg, Germany
Simon Tenbusch: Institute for Operations Research and Management GmbH, 52076 Aachen, Germany

Management Science, 2016, vol. 62, issue 7, 2070-2089

Abstract: 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.Data, as supplemental material, are available at http://dx.doi.org/10.1287/mnsc.2015.2221 . This paper was accepted by Teck-Hua Ho, optimization .

Keywords: mobile networks; frequency allocation; matchings; information systems; enabling technologies; analysis of algorithms; approximation algorithms (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2015.2221 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:62:y:2016:i:7:p:2070-2089

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().