Abstract
We present an approximation algorithm for the minimum bounded degree Steiner network problem that returns a Steiner network of cost at most two times the optimal and the degree on each vertex v is at most min {b v + 3r max , 2b v + 2}, where r max is the maximum connectivity requirement and b v is the given degree bound on v. This unifies, simplifies, and improves the previous results for this problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree bounded directed network design. SIAM Journal on Computing 29, 1413–1431 (2009)
Cheriyan, J., Vegh, L.: Approximating minimum-cost k-node connected subgraphs via independence-free graphs. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2013)
Cheriyan, J., Vempala, S., Vetta, A.: Network design via iterative rounding of setpair relaxations. Combinatorica 26(3), 255–275 (2006)
Fleischer, L., Jain, K., Williamson, D.P.: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. Syst. Sci. 72(5), 838–867 (2006)
Fukunaga, T., Ravi, R.: Iterative rounding approximation algorithms for degree-bounded node-connectivity network design. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 263–272 (2012)
Fürer, M., Raghavachari, B.: Approximating the minimum-degree Steiner tree to within one of optimal. J. of Algorithms 17(3), 409–423 (1994)
Gabow, H.N.: On the L ∞ -norm of extreme points for crossing supermodular directed network LPs. In: Jünger, M., Kaibel, V. (eds.) IPCO 2005. LNCS, vol. 3509, pp. 392–406. Springer, Heidelberg (2005)
Goemans, M.X.: Minimum Bounded-Degree Spanning Trees. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 273–282 (2006)
Jain, K.: A factor 2-approximation algorithm for the generalized steiner network problem. Combinatorica 21(1), 39–60 (2001)
Khandekar, R., Kortsarz, G., Nutov, Z.: On some network design problems with degree constraints. Journal of Computer and System Sciences 79(5), 725–736 (2013)
Király, T., Lau, L.C., Singh, M.: Degree Bounded Matroids and Submodular Flows. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 259–272. Springer, Heidelberg (2008)
Lau, L.C., Naor, S., Salavatipour, M., Singh, M.: Survivable network design with degree or order constraints. SIAM Journal on Computing 39(3), 1062–1087 (2009)
Lau, L.C., Ravi, R., Singh, M.: Iterative Methods in Combinatorial Optimization. Cambridge University Press (2011)
Lau, L.C., Singh, M.: Additive approximation for bounded degree survivable network design. SIAM Journal on Computing 42(6), 2217–2242 (2014)
Louis, A., Vishnoi, N.K.: Improved algorithm for degree bounded survivable network design problem. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, pp. 408–419 (2010)
Nutov, Z.: Degree-constrained node-connectivity. In: Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN), pp. 582–593 (2012)
Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), pp. 661–670 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Lau, L.C., Zhou, H. (2014). A Unified Algorithm for Degree Bounded Survivable Network Design. In: Lee, J., Vygen, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2014. Lecture Notes in Computer Science, vol 8494. Springer, Cham. https://doi.org/10.1007/978-3-319-07557-0_31
Download citation
DOI: https://doi.org/10.1007/978-3-319-07557-0_31
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07556-3
Online ISBN: 978-3-319-07557-0
eBook Packages: Computer ScienceComputer Science (R0)