Improved approximations for shallow-light spanning trees

Joseph Naor, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

We consider the bicriteria optimization problem of computing a shallow-light tree. Given a directed graph with two unrelated cost functions defined on its edges: weight and length, and a designated root vertex, the goal is to find a minimum weight spanning tree such that the path lengths from its root to the rest of the vertices are bounded. This problem has several applications in network and VLSI design, and information retrieval. We give a polynomial time algorithm for finding a spanning tree whose weight is O(log |V|) times the weight of an optimal shallow-light tree, where the path lengths from the root to the rest of the vertices are at most twice the given bounds. We extend our technique to handle two variants of the problem: one in which the length bound is given on the average length of a path from the root to a vertex, and another tricriteria budgeted version. Our paper provides the first non-trivial approximation factors for directed graphs, and improves on previous results for undirected graphs.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science - Proceedings
Pages536-541
Number of pages6
DOIs
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 38th IEEE Annual Symposium on Foundations of Computer Science - Miami Beach, FL, USA
Duration: Oct 20 1997Oct 22 1997

Publication series

NameAnnual Symposium on Foundations of Computer Science - Proceedings
ISSN (Print)0272-5428

Conference

ConferenceProceedings of the 1997 38th IEEE Annual Symposium on Foundations of Computer Science
CityMiami Beach, FL, USA
Period10/20/9710/22/97

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Improved approximations for shallow-light spanning trees'. Together they form a unique fingerprint.

Cite this