An $O(k^3\log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design

by Julia Chuzhoy and Sanjeev Khanna

Theory of Computing, Volume 8(18), pp. 401-413, 2012

Bibliography with links to cited articles

[1]   Ajit Agrawal, Philip Klein, and R. Ravi: When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput., 24(3):440–456, 1995. Preliminary version in STOC’91. [doi:10.1137/S0097539792236237]

[2]   Marshall Bern and Paul Plassmann: The Steiner problem with edge lengths 1 and 2. Inform. Process. Lett., 32(4):171–176, 1989. [doi:10.1016/0020-0190(89)90039-2]

[3]   Tanmoy Chakraborty, Julia Chuzhoy, and Sanjeev Khanna: Network design for vertex connectivity. In Proc. 40th STOC, pp. 167–176. ACM Press, 2008. [doi:10.1145/1374376.1374403]

[4]   Chandra Chekuri and Nitish Korula: Single-sink network design with vertex connectivity requirements. In IARCS Ann. Conf. on Foundations of Software Tech. and Theor. Comput. Sci. (FSTTCS’08), pp. 131–142. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2008. [doi:10.4230/LIPIcs.FSTTCS.2008.1747]

[5]   Chandra Chekuri and Nitish Korula: A graph reduction step preserving element-connectivity and applications. In Proc. 36th Internat. Colloq. on Automata, Languages and Programming (ICALP’09), pp. 254–265. Springer, 2009. [doi:10.1007/978-3-642-02927-1_22]

[6]   Joseph Cheriyan, Santosh Vempala, and Adrian Vetta: An approximation algorithm for the minimum-cost k-vertex connected subgraph. SIAM J. Comput., 32(4):1050–1055, 2003. Preliminary version in STOC’02. [doi:10.1137/S0097539701392287]

[7]   Joseph Cheriyan, Santosh Vempala, and Adrian Vetta: Network design via iterative rounding of setpair relaxations. Combinatorica, 26(3):255–275, 2006. [doi:10.1007/s00493-006-0016-z]

[8]   Julia Chuzhoy and Sanjeev Khanna: Algorithms for single-source vertex connectivity. In Proc. 49th FOCS, pp. 105–114. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.63]

[9]   Arkadiĭ G. D’yachkov and Vyacheslav V. Rykov: Bounds on the length of disjunctive codes. Probl. Peredachi Inf., 18:7–13, 1982. [Math-Net.ru].

[10]   Jittat Fakcharoenphol and Bundit Laekhanukit: An O(log 2k)-approximation algorithm for the k-vertex connected spanning subgraph problem. In Proc. 40th STOC, pp. 153–158. ACM Press, 2008. [doi:10.1145/1374376.1374401]

[11]   Lisa Fleischer: A 2-approximation for minimum cost {0, 1, 2} vertex connectivity. In Proc. 8th Ann. Conf. on Integer Programming and Combinatorial Optimization (IPCO ’01), pp. 115–129. Springer, 2001. [doi:10.1007/3-540-45535-3_10]

[12]   Lisa Fleischer, Kamal Jain, and David P. Williamson: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. System Sci., 72(5):838–867, 2006. Preliminary version in FOCS’01. [doi:10.1016/j.jcss.2005.05.006]

[13]   András Frank and Tibor Jordán: Minimal edge-coverings of pairs of sets. J. Combin. Theory Ser. B, 65(1):73–110, 1995. [doi:10.1006/jctb.1995.1044]

[14]   Zoltán Füredi: On r-cover-free families. J. Combin. Theory Ser. A, 73(1):172–173, 1996. [doi:10.1006/jcta.1996.0012]

[15]   Kamal Jain: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39–60, 2001. Preliminary version in FOCS’98. [doi:10.1007/s004930170004]

[16]   Kamal Jain, Ion Măndoiu, Vijay V. Vazirani, and David P. Williamson: A primal-dual schema based approximation algorithm for the element connectivity problem. J. Algorithms, 45(1):1–15, 2002. Preliminary version in SODA’99. [doi:10.1016/S0196-6774(02)00222-5]

[17]   Guy Kortsarz, Robert Krauthgamer, and James R. Lee: Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput., 33(3):704–720, 2004. Preliminary version in APPROX’02. [doi:10.1137/S0097539702416736]

[18]   Guy Kortsarz and Zeev Nutov: Approximating k-node connected subgraphs via critical graphs. SIAM J. Comput., 35(1):247–257, 2005. Preliminary version in STOC’04. [doi:10.1137/S0097539703435753]

[19]   Ravi Kumar, Sridhar Rajagopalan, and Amit Sahai: Coding constructions for blacklisting problems without computational assumptions. In 19th Ann. Internat. Cryptology Conf. (CRYPTO’99), pp. 609–623. Springer, 1999. [doi:10.1007/3-540-48405-1_38]

[20]   Yuval Lando and Zeev Nutov: Inapproximability of survivable networks. Theoret. Comput. Sci., 410(21-23):2122–2125, 2009. Preliminary version in APPROX’08. [doi:10.1016/j.tcs.2009.01.036]

[21]   Rajeev Motwani and Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press, 1995.

[22]   Zeev Nutov: An almost O(log k)-approximation for k-connected subgraphs. In Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’09), pp. 912–921. ACM Press, 2009. [ACM:1496770.1496869]

[23]   Zeev Nutov: Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions. In Proc. 50th FOCS, pp. 417–426. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.9]

[24]   Zeev Nutov: A note on rooted survivable networks. Inform. Process. Lett., 109(19):1114–1119, 2009. [doi:10.1016/j.ipl.2009.07.011]

[25]   Douglas R. Stinson, Ruizhong Wei, and Lie Zhu: Some new bounds for cover-free families. J. Combin. Theory Ser. A, 90(1):224–234, 2000. [doi:10.1006/jcta.1999.3036]