Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/1674
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Koller, AE | - |
dc.contributor.author | Noble, SD | - |
dc.coverage.spatial | 10 | en |
dc.date.accessioned | 2008-02-20T09:41:17Z | - |
dc.date.available | 2008-02-20T09:41:17Z | - |
dc.date.issued | 2004 | - |
dc.identifier.citation | Discrete Mathematics 275(1-3): 331-338, Jan 2004 | en |
dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/1674 | - |
dc.description.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$. | en |
dc.format.extent | 114059 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | Elsevier | en |
dc.subject | Frequency Assignment Problem | en |
dc.subject | Greedy Heuristic | en |
dc.subject | Domination Number | en |
dc.title | Domination Analysis of Greedy Heuristics For The Frequency Assignment Problem | en |
dc.type | Preprint | en |
dc.identifier.doi | http://dx.doi.org/10.1016/j.disc.2003.05.008 | - |
Appears in Collections: | Computer Science Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
DomFAPref2.pdf | 111.39 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.