On the convergence of a randomized algorithm for a frequency assignment problem

On the convergence of a randomized algorithm for a frequency assignment problem

0.00 Avg rating0 Votes
Article ID: iaor2001954
Country: Slovakia
Volume: 6
Issue: 1/2
Start Page Number: 135
End Page Number: 151
Publication Date: Jan 1998
Journal: Central European Journal of Operations Research
Authors:
Keywords: heuristics, graphs
Abstract:

The problems of assigning frequencies to transmitters can be naturally modeled by generalizations of graph coloring problems. We consider the problem of minimizing the number of constraints violated when the set of available frequencies is fixed. We prove that the Markov chain corresponding to a randomized algorithm for this problem based of the 3-coloring algorithm of Petford and Welsh is ergodic.

Reviews

Required fields are marked *. Your email address will not be published.