A primal-dual schema based approximation algorithm for the element connectivity problem

Keywords

Disjoint sets, Approximation algorithm, Vertex (graph theory), Schema (genetic algorithms), Element (criminal law)

References

• A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraphs (New Developments of Theory of Computation and Algorithms)仁 永持, 俊秀 茨木 — 2001
• Design of Survivable NetworksMechthild Stoer — 1993
• The primal-dual method for approximation algorithms and its application to network design problemsMichel X. Goemans, David P. Williamson — 1996
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity ConstraintsMartin Grötschel, Clyde Monma, Mechthild Stoer — 1992
• A commercial application of survivable network design: ITP/INPLANS CCS network topology analyzerMilena Mihail, David Shallcross, Nate Dean — 1996
• A primal-dual approximation algorithm for generalized steiner network problemsDavid P. Williamson, Michel X. Goemans, Milena Mihail — 1993
• Improved approximation algorithms for network design problemsM. X. Goemans, Andrew V. Goldberg, Serge Plotkin — 1994
• Approximation Algorithms for NP-Hard ProblemsDorit S. Hochba — 1997
• Methods for Designing Communications Networks with Certain Two-Connected Survivability ConstraintsClyde Monma, David Shallcross — 1989
• Improved approximation algorithms for uniform connectivity problemsSamir Khuller, Balaji Raghavachari — 1995
• Augmenting graphs to meet edge-connectivity requirementsAndrás Frank — 1990
• An iterative rounding 2-approximation algorithm for the element connectivity problemLisa Fleischer, Kamal Jain, David P. Williamson — 2001
• A Factor 2 Approximation Algorithm for the Generalized Steiner Network ProblemKamal Jain — 1998
• An approximation algorithm for minimum-cost vertex-connectivity problemsR. Ravi, David P. Williamson — 1997
• Augmenting Graphs to Meet Edge-Connectivity RequirementsAndrás Frank — 1992
• A primal-dual schema based approximation algorithm for the element connectivity problemKamal Jain, Ion Măndoiu, Vijay V. Vazirani — 1999
• Improved Approximation Algorithms for Uniform Connectivity ProblemsSamir Khuller, Balaji Raghavachari — 1996
• A primal-dual approximation algorithm for generalized steiner network problemsDavid P. Williamson, Michel X. Goemans, Milena Mihail — 1995
• A 2-approximation for Minimum Cost 0, 1, 2 Vertex ConnectivityG. F. J-SJ, Berry Lt, U. Kla — 2001

Cited by

• Approximation Algorithms for Network Design and OrienteeringChandra Chekuri, Nitish Korula — 2010
• Iterative Rounding Approximation Algorithms in Network DesignMarcus Shea — 2010
• A Deterministic Algorithm for the Vertex Connectivity Survivable Network Design ProblemPushkar Tripathi — 2010
• Primal-dual approximation algorithms for metric facility location and k-median problemsKamal Jain, Vijay V. Vazirani — 1999
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problemsLisa Fleischer, Kamal Jain, David P. Williamson — 2006
• Network Design Via Iterative Rounding Of Setpair RelaxationsJoseph Cheriyan, Santosh Vempala, Adrian Vetta — 2006
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected SubgraphJoseph Cheriyan, Santosh Vempala, Adrian Vetta — 2003
• Packing element-disjoint steiner treesJoseph Cheriyan, Mohammad R. Salavatipour — 2005
• Approximation algorithms for minimum-cost k-vertex connected subgraphsJoseph Cheriyan, Santosh Vempala, Adrian Vetta — 2002
• Connectivity Upgrade Models for Survivable Network DesignAnantaram Balakrishnan, Prakash Mirchandani, Harihara Prasad Natarajan — 2009
• A primal-dual approximation algorithm for the survivable network design problem in hypergraphsLiang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki — 2001
• Hardness of Approximation for Vertex-Connectivity Network Design ProblemsGuy Kortsarz, Robert Krauthgamer, James R. Lee — 2002
• A Graph Reduction Step Preserving Element-Connectivity and Packing Steiner Trees and ForestsChandra Chekuri, Nitish Korula — 2014
• Approximate Min-Max Theorems of Steiner Rooted-Orientations of HypergraphsTamás Király, Lap Lau — 2006
• Approximation algorithms for network design: A surveyAnupam Gupta, Jochen Könemann — 2011
• Approximating a class of combinatorial problems with rational objective functionJosé Correa, Cristina G. Fernandes, Yoshiko Wakabayashi — 2010
• Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxationKamal Jain, Vijay V. Vazirani — 2001
• An iterative rounding 2-approximation algorithm for the element connectivity problemLisa Fleischer, Kamal Jain, David P. Williamson — 2001
• A Factor 2 Approximation Algorithm for the Generalized Steiner Network ProblemKamal Jain — 1998
• Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphsTamás Király, Lap Chi Lau — 2008

Related papers

• A Bipartite Analogue of Dilworth’s TheoremJacob Fox — 2006
• Almost Disjoint Triangles in 3-SpaceKárolyi, József Solymosi — 2002
• Hierarchical b-MatchingYuval Emek, Shay Kutten, Mordechai Shalom — 2019
• The irregularity strength of the disjoint union of butterfly graphsF. A. N. J. Apituley, M. W. Talakua, Yopi Andry Lesnussa — 2023
• Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphsToshimasa Ishii — 2009
• ON THE IRREGULARITY STRENGTH AND MODULAR IRREGULARITY STRENGTH OF FRIENDSHIP GRAPHS AND ITS DISJOINT UNIONFredrylo Alberth Noel Joddy Apituley, Mozart W. Talakua, Yopi Andry Lesnussa — 2022
• Structure of vertex-transitive graphsAlwin C Green — 1975
• All regular multipartite tournaments that are cycle complementaryLutz Volkmann — 2004