Abstract
We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an edge weighted graph G = (V, E), in the edge based upgrading model, it is assumed that each edge e of the given network also has an associated function ce (t) that specifies the cost of upgrading the edge by an amount t. A reduction strategy specifies for each edge e the amount by which the length ℓ(e) is to be reduced. In the node based upgrading model, a node v can be upgraded at an expense of c(v). Such an upgrade reduces the delay of each edge incident on v. For a given budget B, the goal is to find an improvement strategy such that the total cost of reduction is at most the given budget B and the cost of a subgraph (e.g. minimum spanning tree) under the modified edge lengths is the best over all possible strategies which obey the budget constraint.
After providing a brief overview of the models and definitions of the various problems considered, we present several new results on the complexity and approximability of network improvement problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, “Proof verification and intractability of approximation problems,” in Proceedings of the 33rd Annual IEEE Symposium on the Foundations of Computer Science (FOCS'92), October 1992, pp. 13-23.
O. Berman, “Improving the location of minisum facilities through network modification,” Annals of Operations Research vol. 40, pp. 1-16, 1992.
M. Bellare, O. Goldreich, and M. Sudan, “Free bits, PCPs and non-approximability - towards tight results,” in Proceedings of the 36th Annual IEEE Symposium on the Foundations of Computer Science (FOCS'95), 1995, pp. 422-431.
M. W. Bern, E. L. Lawler and A. L. Wong, “Linear-Time Computation of Optimal Subgraphs of Decomposable Graphs,” Journal of Algorithms vol. 8, pp. 216-235, 1987.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, McGraw-Hill Book Co.: Cambridge, MA, 1990.
J. Edmonds and E. L. Johnson, “Matching, Euler tours and the Chinese postman,” Mathematical Programming, vol. 5, 88-124, 1973.
G. N. Frederickson and R. Solis-Oba, “Increasing the weight of minimum spanning tree,” in Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'96), January 1996, pp. 539-546.
M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory ofNP-completeness, W. H. Freeman and Company: San Francisco, CA, 1979.
M. W. Goemans and D. P. Williamson, “A general approximation technique for constrained forest problems,” SIAM Journal on Computing vol. 24, pp. 296-317, 1995.
M. M. Halldórsson, “Approximating the minimum maximal independence number,” Information Processing Letters vol. 46, pp. 169-172, 1993.
R. Hassin, “Approximation schemes for the restricted shortest path problem,” Mathematics of Operations Research vol. 17, pp. 36-42, 1992.
S. E. Hambrusch and H. Y. Tu, “Edge Weight Reduction Problems in Acyclic graphs,” J. Algorithms vol. 24, pp. 66-93, 1997.
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe, and K. U. Drangmeister, “Modifying Edges of a Network to Obtain Short Subgraphs,” Accepted for publication in Theoretical Computer Science. (An extended abstract of this paper titled Modifying networks to obtain low cost treesappeared in Proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, Cadenabbia, Italy, Lecture Notes in Computer Science, June 1996, pp. 293-307.)
S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, and H. C. Wirth, “Improving Spanning Trees by Upgrading Nodes,” in Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97), Bologna, Italy, July 1997, pp. 281-291.
D. Karger and S. Plotkin, “Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows,” in Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (STOC'95), May 1995, pp. 18-25.
E. L. Lawler, Combinatorial optimization: Networks and matroids, Holt, Rinehart and Winston, 1976.
L. Lovász and M. D. Plummer, Matching theory, Akadémiai Kiadó, Budapest (1986), 1986.
M. V. Marathe, R. Ravi, R. Sundaram, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt III, “Bicriteria network design problems,” in Proceedings of the 22nd International Colloquium on Automata, Languages and Programming (ICALP'95), July 1995, pp. 487-498.
C. Phillips, “The network inhibition problem,” in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC'93), May 1993, pp. 288-293.
J. Plesnik, “The complexity of designing a network with minimum diameter,” Networks vol. 11, pp. 77-85, 1981.
D. Paik and S. Sahni, “Network upgrading problems,” Networks vol. 26, pp. 45-58, 1995.
C. H. Papadimitriou and M. Yannakakis, “Optimization, approximation, and complexity classes,” Journal of computer and system sciences vol. 43, pp. 425-440, 1991.
R. Ravi, Steiner trees and beyond, Ph.D. thesis, Brown University, Providence, Rhode Island 02912, USA, 1993.
R. Ravi, “Rapid rumor ramification,” in Proceedings of the 35th Annual IEEE Symposium on the Foundations of Computer Science (FOCS'94), November 1994, pp. 202-213.
R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt III, “Many birds with one stone: Multi-objective approximation algorithms,” in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC'93), May 1993, pp. 438-447.
A. Warburton, “Approximation of pareto optima in multiple-objective shortest path problems,” Operations Research vol. 35, pp. 70-79, 1992.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Krumke, S.O., Marathe, M.V., Noltemeier, H. et al. Approximation Algorithms for Certain Network Improvement Problems. Journal of Combinatorial Optimization 2, 257–288 (1998). https://doi.org/10.1023/A:1009798010579
Issue Date:
DOI: https://doi.org/10.1023/A:1009798010579