TY - GEN

T1 - Improved approximations for shallow-light spanning trees

AU - Naor, Joseph

AU - Schieber, Baruch

PY - 1997/12/1

Y1 - 1997/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0031352177&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031352177&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1997.646142

DO - 10.1109/SFCS.1997.646142

M3 - Conference contribution

AN - SCOPUS:0031352177

SN - 0818681977

T3 - Annual Symposium on Foundations of Computer Science - Proceedings

SP - 536

EP - 541

BT - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - Proceedings of the 1997 38th IEEE Annual Symposium on Foundations of Computer Science

Y2 - 20 October 1997 through 22 October 1997

ER -