Improving Steiner trees of a network under multiple constraints

Sven O. Krumke, Hartmut Noltemeier, Madha V. Marathe, R. Ravi, S. S. RaviUniversity 1996 · OpenAlex

Abstract

The authors consider the problem of decreasing the edge weights of a given network so that the modified network has a Steiner tree in which two performance measures are simultaneously optimized. They formulate these problems, referred to as bicriteria network improvement problems, by specifying a budget on the total modification cost, a constraint on one of the performance measures and using the other performance measure as a minimization objective. Network improvement problems are known to be NP-hard even when only one performance measure is considered. The authors present the first polynomial time approximation algorithms for bicriteria network improvement problems. The approximation algorithms are for two pairs of performance measures, namely (diameter, total cost) and (degree, total cost). These algorithms produce solutions which are within a logarithmic factor of the optimum value of the minimization objective while violating the constraints only by a logarithmic factor. The techniques also yield approximation schemes when the given network has bounded treewidth. Many of the approximation results can be extended to more general network design problems.
BibTeX
@inproceedings{krumke1996improving,
  author = {Sven O. Krumke and Hartmut Noltemeier and Madha V. Marathe and R. Ravi and S. S. Ravi},
  title = {{Improving Steiner trees of a network under multiple constraints}},
  booktitle = {University},
  year = {1996},
}

Loading related content...

Figure