2009 | OriginalPaper | Chapter
Three Results on Frequency Assignment in Linear Cellular Networks
(Extended Abstract)
Authors : Marek Chrobak, Jiří Sgall
Published in: Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In the frequency assignment problem we are given a graph representing a wireless network and a sequence of requests, where each request is associated with a vertex. Each request has two more attributes: its arrival and departure times, and it is considered active from the time of arrival to the time of departure. We want to assign frequencies to all requests so that at any time no two active requests associated with the same or adjacent nodes use the same frequency. The objective is to minimize the number of frequencies used.
We focus exclusively on the special case of the problem when the underlying graph is a linear network (path). For this case, we consider both the offline and online versions of the problem, and we present three results. First, in the incremental online case, where the requests arrive over time, but never depart, we give an algorithm with an optimal (asymptotic) competitive ratio
$\frac{4}{3}$
. Second, in the general online case, where the requests arrive and depart over time, we improve the current lower bound on the (asymptotic) competitive ratio to
$\frac{11}{7}$
. Third, we prove that the offline version of this problem is
${\mathbb {NP}}$
-complete.