Channel Assignment with Large Demands

Stefanie Gerke and Colin McDiarmid

Annals of Operations Research, 2001, vol. 107, issue 1, 143-159

Abstract: We introduce a general static model for radio channel assignment, the ‘feasible assignments model’, in which to investigate the effects of changes in demand. For a fixed instance of this model where only the demands can vary, we consider the span of spectrum needed for a feasible assignment of channels to transmitters, and compare this span with a collection of lower bounds, in the limit when demands at the transmitters get large. We introduce a relevant measure which generalises the imperfection ratio of a graph and give alternative descriptions. We show that for a fixed instance of the feasible assignments model where only the demands can vary, on input the demands we can find the span in polynomial time. For the special case when the feasible assignments can be described by means of a complete graph together with co-site and adjacent constraints, we give a formula for the span. This yields clique-based lower bounds for the span in general problems. Copyright Kluwer Academic Publishers 2001

Keywords: channel assignment; graph imperfection; clique-bounds (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1014951015725 (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:107:y:2001:i:1:p:143-159:10.1023/a:1014951015725

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1014951015725

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().