Brunel University Research Archive (BURA) >
Research Areas >
Information Systems and Computing >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/1674

Title: Domination Analysis of Greedy Heuristics For The Frequency Assignment Problem
Authors: Koller, AE
Noble, SD
Keywords: Frequency Assignment Problem
Greedy Heuristic
Domination Number
Publication Date: 2004
Publisher: Elsevier
Citation: Discrete Mathematics 275(1-3): 331-338, Jan 2004
Abstract: We introduce the greedy expectation algorithm for the fixed spectrum version of the frequency assignment problem. This algorithm was previously studied for the travelling salesman problem. We show that the domination number of this algorithm is at least $\sigma^{n-\lceil\log_2 n\rceil-1}$ where $\sigma$ is the available span and $n$ the number of vertices in the constraint graph. In contrast to this we show that the standard greedy algorithm has domination number strictly less than $\sigma^{n}e^{-\frac{5(n-1)}{144}}$ for large n and fixed $\sigma$.
URI: http://bura.brunel.ac.uk/handle/2438/1674
DOI: http://dx.doi.org/10.1016/j.disc.2003.05.008
Appears in Collections:Mathematics
Information Systems and Computing

Files in This Item:

File Description SizeFormat
DomFAPref2.pdf111.39 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan