Designing networks with bounded pairwise distance

Yevgeniy Dodis, Sanjeev Khanna

Research output: Contribution to journalConference articlepeer-review


The problem of finding a minimum cost subset of missing links in a communication network was considered, such that adding these links to the network makes every pair of points within distance at most d from each other. A novel linear programming based approach was used to obtain an O(log n log d) approximation algorithm for the case of uniform link lengths and costs. The Ω(log n) hardness was also extended to d∈{2, 3}. On the other hand, if link costs can vary, it was shown that the problem is Ω(2log(1-ε)n)-hard for d≥3.

Original languageEnglish (US)
Pages (from-to)750-759
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 1999
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Designing networks with bounded pairwise distance'. Together they form a unique fingerprint.

Cite this