### Abstract

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 Ω(2^{log(1-ε)n})-hard for d≥3.

Original language | English (US) |
---|---|

Pages (from-to) | 750-759 |

Number of pages | 10 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

State | Published - 1999 |

Event | Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA Duration: May 1 1999 → May 4 1999 |

### ASJC Scopus subject areas

- Software

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

## Cite this

Dodis, Y., & Khanna, S. (1999). Designing networks with bounded pairwise distance.

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*, 750-759.