Download now Free registration required
Given a complete undirected graph, a cost function on edges and a degree bound B, the degree bounded network design problem is to find a minimum cost simple subgraph with maximum degree B satisfying given connectivity requirements. Even for simple connectivity requirement such as finding a spanning tree, computing a feasible solution for the degree bounded network design problem is already NP-hard, and thus there is no polynomial factor approximation algorithm for this problem. This paper shows that when the cost function satisfies triangle inequalities, there are constant factor approximation algorithms for various degree bounded network design problems.
- Format: PDF
- Size: 179.7 KB