Matrix columns allocation problems

Orthogonal Frequency Division Multiple Access (OFDMA) transmission technique is gaining popularity as a preferred technique in the emerging broadband wireless access standards. Motivated by the OFDMA transmission technique we define the following problem: Let M be a matrix (over R ) of size a × b ....

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2009-05, Vol.410 (21), p.2174-2183
Main Authors: Beimel, Amos, Ben-Moshe, Boaz, Ben-Shimol, Yehuda, Carmi, Paz, Chai, Eldad, Kitroser, Itzik, Omri, Eran
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Allocation problems
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
inapproximability
Miscellaneous
NP-completeness
Theoretical computing
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Orthogonal Frequency Division Multiple Access (OFDMA) transmission technique is gaining popularity as a preferred technique in the emerging broadband wireless access standards. Motivated by the OFDMA transmission technique we define the following problem: Let M be a matrix (over R ) of size a × b . Given a vector of non-negative integers C → = 〈 c 1 , c 2 , … , c b 〉 such that ∑ c j = a , we would like to allocate a cells in M such that (i) in each row of M there is a single allocation, and (ii) for each element c i ∈ C → there is a unique column in M which contains exactly c i allocations. Our goal is to find an allocation with minimal value, that is, the sum of all the a cells of M which were allocated is minimal. The nature of the suggested new problem is investigated in this paper. Efficient algorithms are suggested for some interesting cases. For other cases of the problem, NP-hardness proofs are given followed by inapproximability results.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2009.02.015