×

zbMATH — the first resource for mathematics

A primal-dual approximation algorithm for generalized Steiner network problems. (English) Zbl 0838.90133
Summary: We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem. If \(k\) is the maximum cut requirement of the problem, our solution comes within a factor of \(2k\) of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.

MSC:
90C35 Programming involving graphs or networks
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Agrawal, P. Klein, andR. Ravi: ?When trees collide: An approximation algorithm for the generalized Steiner problem in networks?,Proc. 23rd ACM Symp. on Theory of Computing, 134-144 (1991).
[2] P. Berman andV. Ramaiyer: ?Improved approximations for the Steiner tree problem?,Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, 325-334 (1992). · Zbl 0829.68063
[3] G. Dobson: ?Worst-case analysis of greedy heuristics for integer programming with non-negative data?,Math. of Oper. Res. 7, 515-531 (1982). · Zbl 0498.90061
[4] G. N. Frederickson andJ. Ja’Ja’: ?Approximation algorithms for several graph augmentation problems?,SIAM J. Comput. 10, 270-283 (1981). · Zbl 0461.05040
[5] H. N. Gabow, M. X. Goemans, andD. P. Williamson: ?An Efficient Approximation algorithm for the survivable network design problem?,Proc. Third Conference on Integer Programming and Combinatorial Optimization, 57-74 (1993). · Zbl 0923.90136
[6] M. X. Goemans andD. J. Bertsimas: ?Survivable networks, linear programming relaxations and the parsimonious property?,Math. Programming,60, 145-166 (1993). · Zbl 0790.90072
[7] M. X. Goemans, A. V. Goldberg, S. Plotkin, D. B. Shmoys, É. Tardos andD. P. Williamson: ?Improved approximation algorithms for network design problems?,Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, 223-232 (1994). · Zbl 0873.68005
[8] M. X. Goemans andD. P. Williamson: ?A general approximation technique for constrained forest problems?,Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, 307-316 (1992). To appear inSIAM J. on Comput. · Zbl 0818.90124
[9] M. Grötschel, C. L. Monma andM. Stoer: ?Design of survivable networks?, to appear in theHandbook in Operations Research and Management Science, Eds: Michael Ball, Thomas Magnanti, Clyde Monma, and George Nemhauser (1992).
[10] N. G. Hall andD. S. Hochbaum: ?A fast approximation algorithm for the multicovering problem?,Disc. Appl. Math. 15, 35-40 (1986). · Zbl 0602.90110
[11] S. Khuller andU. Vishkin: ?Biconnectivity approximations and graph carvings?, Technical Report UMIACS-TR-91-132, Univ. of Maryland (September 1991). Also appears inProc. 24th ACM Symp. on Theory of Computing, 759-770 (1992).
[12] P. Klein andR. Ravi: ?When cycles collapse: A general approximation technique for constrained two-connectivity problems?,Proc. Third Conference on Integer Programming and Combinatorial Optimization, 39-55 (1993). · Zbl 0942.68651
[13] D. Naor, D. Gusfield, andC. Martel: ?A fast algorithm for optimally increasing the edge-connectivity?,Proc. 31st Annual Symp. on Foundations of Computer Science, 698-707 (1990).
[14] C. H. Papadimitriou andK. Steiglitz:Combinatorial Optimization: Algorithms and Complexity, Englewood Cliffs, NJ: Prentice-Hall (1982). · Zbl 0503.90060
[15] S. Rajagopalan andV. V. Vazirani: ?Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs?,Proc. 34th Annual Symp. on Foundations of Computer Science, 322-331 (1993).
[16] H. Saran, V. Vazirani, andN. Young: ?A primal-dual approach to approximation algorithms for network Steiner problems?,Proc. of Indo-US workshop on Cooperative Research in Computer Science, Bangalore, India, 166-168 (1992).
[17] A. Z. Zelikovsky: ?An 11/6-approximation algorithm for the network Steiner problem?,Algorithmica,9, 463-470 (1993). · Zbl 0768.68192
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.