Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/1674
DC FieldValueLanguage
dc.contributor.authorKoller, AE-
dc.contributor.authorNoble, SD-
dc.coverage.spatial10en
dc.date.accessioned2008-02-20T09:41:17Z-
dc.date.available2008-02-20T09:41:17Z-
dc.date.issued2004-
dc.identifier.citationDiscrete Mathematics 275(1-3): 331-338, Jan 2004en
dc.identifier.urihttp://bura.brunel.ac.uk/handle/2438/1674-
dc.description.abstractWe 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$.en
dc.format.extent114059 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.publisherElsevieren
dc.subjectFrequency Assignment Problemen
dc.subjectGreedy Heuristicen
dc.subjectDomination Numberen
dc.titleDomination Analysis of Greedy Heuristics For The Frequency Assignment Problemen
dc.typePreprinten
dc.identifier.doihttp://dx.doi.org/10.1016/j.disc.2003.05.008-
Appears in Collections:Computer Science
Mathematical Sciences

Files in This Item:
File Description SizeFormat