Near-optimal service facility location in dynamic communication networks

A. Liotta, C. Ragusa, G. Pavlou

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)


Systems relying on increasingly large and dynamic communication networks must find effective ways to optimally localize service facilities. This can be achieved by efficiently partitioning the system and computing the partitions' centers, solving the classic p-median and p-center problems. These are NP-hard when striving for optimality. Numerous approximate solutions have been proposed during the past 30 years. However, they all fail to address the combined requirements of scalability, optimality and flexibility. Here we present a novel distributed algorithm that computes provably near-optimal p-medians in linear time, exploiting the properties of mobile software agents.
Original languageEnglish
Pages (from-to)862-864
JournalIEEE Communications Letters
Issue number9
Publication statusPublished - 2005


Dive into the research topics of 'Near-optimal service facility location in dynamic communication networks'. Together they form a unique fingerprint.

Cite this