Distributed Online Frequency Assignment in Cellular Networks

Jeannette Janssen, Danny Krizanc, Lata Narayanan, Sunil Shende

Research output: Contribution to journalArticle

47 Scopus citations


A cellular network is generally modeled as a subgraph of the triangular lattice. The distributed online frequency assignment problem can be abstracted as a multi-coloring problem on a weighted graph, where the weight vector associated with the vertices models the number of calls to be served at the vertices and is assumed to change over time. In this paper, we develop a framework for studying distributed online frequency assignment in cellular networks. We present the first distributed online algorithms for this problem with proven bounds on their competitive ratios. We show a series of algorithms that use at each vertex information about increasingly larger neighborhoods of the vertex, and that achieve better competilive ratios. In contrast, we show lower bounds on the competitive ratios of some natural classes of online algorithms.

Original languageEnglish (US)
Pages (from-to)119-151
Number of pages33
JournalJournal of Algorithms
Issue number2
StatePublished - Aug 2000

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Distributed Online Frequency Assignment in Cellular Networks'. Together they form a unique fingerprint.

  • Cite this