Upper and lower bounding techniques for frequency assignment problems

C.A.J. Hurkens, S.R. Tiourine

Research output: Book/ReportReportAcademic

63 Downloads (Pure)

Abstract

We consider two variants of the radio link frequency assignment problem??. These problems arise in practice when a network of radio links has to be established??. Each radio link has to be assigned a particular frequency??. The interference level between the frequencies assigned to the di??erent links has to be acceptable??, since otherwise communication will be distorted.?? The frequency assignments have to comply with certain regulations and physical characteristics of the transmitters.?? Moreover??, the number of frequencies is to be minimized, because each frequency used in the network has to be reserved at a certain cost??. We develop several approximation algorithms for the problems??, which are based on local search,?? and we compare their performance on some practical instances.?? Lower bounding techniques based on nonlinear programming and the chromatic number of a graph are used to estimate the quality of the approximate solutions for these instances??.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages22
Publication statusPublished - 1995

Publication series

NameMemorandum COSOR
Volume9534
ISSN (Print)0926-4493

Fingerprint Dive into the research topics of 'Upper and lower bounding techniques for frequency assignment problems'. Together they form a unique fingerprint.

Cite this