Loading...
Please wait, while we are loading the content...
Similar Documents
Approximation algorithms for degree-constrained minimum-cost network-design problems
| Content Provider | CiteSeerX |
|---|---|
| Author | Ravi, R. Marathe, Madhav V. Ravi, S. S. Rosenkrantz, Daniel J. Hunt Iii, Harry B. |
| Abstract | We study network-design problems with two different design objectives: the total cost of the edges and nodes in the network and the maximum degree of any node in the network. A prototypical example is the degree-constrained node-weighted Steiner tree problem: We are given an undirected graph, with a non-negative integral function that specifies an upper bound on the degree of each vertex in the Steiner tree to be constructed, nonnegative costs on the nodes, and a subset of nodes called terminals. The goal is to construct a Steiner tree containing all the terminals such that the degree of any node in is at most the specified upper bound and the total cost of the nodes in is minimum. Our main result is a bicriteria approximation algorithm whose output is approximate in terms of both the degree and cost criteria – the degree of any node in the output Steiner tree is and the cost of the tree is times that of a minimum-cost Steiner tree that obeys the degree bound for each node. Our result extends to the more general problem of constructing one-connected networks such as generalized Steiner forests. We also consider the special case in which the edge costs obey the triangle inequality and present simple approximation algorithms with better performance guarantees. |
| File Format | |
| Journal | Algorithmica |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Approximation Algorithm Degree-constrained Minimum-cost Network-design Problem Steiner Tree Upper Bound Total Cost Generalized Steiner Forest Degree-constrained Node-weighted Steiner Tree Problem Prototypical Example Main Result Minimum-cost Steiner Tree Special Case Output Steiner Tree Triangle Inequality Undirected Graph General Problem One-connected Network Performance Guarantee Non-negative Integral Function Maximum Degree Degree Bound Cost Criterion Different Design Objective Nonnegative Cost Present Simple Approximation Algorithm Network-design Problem Bicriteria Approximation Algorithm |
| Content Type | Text |
| Resource Type | Article |
