scientific article
From MaRDI portal
Publication:3128880
zbMath0873.68005MaRDI QIDQ3128880
Michel X. Goemans, David P. Williamson, Andrew V. Goldberg, David B. Shmoys, Éva Tardos, Serge A. Plotkin
Publication date: 23 April 1997
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Programming involving graphs or networks (90C35) Network design and communication in computer systems (68M10) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)
Related Items
Flexible Graph Connectivity, Incremental network design with shortest paths, Improved approximation algorithms for minimum cost node-connectivity augmentation problems, Approximation Algorithms for Multi-budgeted Network Design Problems, A primal-dual approximation algorithm for generalized Steiner network problems, An automated network generation procedure for routing of unmanned aerial vehicles (UAVs) in a GIS environment, Design of Survivable Networks: A survey, New primal-dual algorithms for Steiner tree problems, The parsimonious property of cut covering problems and its applications, On the tree augmentation problem, Rounding algorithms for covering problems, Fast Distributed Approximation for TAP and 2-Edge-Connectivity, A Spectral Approach to Network Design, Unnamed Item, A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract), On the approximability of some maximum spanning tree problems, On the approximability of some Maximum Spanning Tree Problems, Node connectivity augmentation via iterative randomized rounding, Correlation clustering and two-edge-connected augmentation for planar graphs, Approximation algorithms for flexible graph connectivity, Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree, Unnamed Item, Approximating covering integer programs with multiplicity constraints, GMPLS label space minimization through hypergraph layouts, Approximating k-Connected m-Dominating Sets, On the cycle augmentation problem: hardness and approximation algorithms, An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem, Fractional routing using pairs of failure-disjoint paths, Linear bounds for on-line Steiner problems, A \(4+\epsilon\) approximation for \(k\)-connected subgraphs, Approximability of Capacitated Network Design, An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity, An O(logn)-Competitive Algorithm for Online Constrained Forest Problems, An approximation algorithm for minimum-cost vertex-connectivity problems, Fast distributed approximation for TAP and 2-edge-connectivity, Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs, Complexity of minimum irreducible infeasible subsystem covers for flow networks, A tight algorithm for strongly connected Steiner subgraph on two terminals with demands, Online constrained forest and prize-collecting network design, Approximating source location and star survivable network problems, Upgrading bottleneck constrained forests, Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems, On survivable network polyhedra, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs, Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems, Network flow spanners, A note on Rooted Survivable Networks, Approximation of Steiner forest via the bidirected cut relaxation, Approximating Steiner Networks with Node Weights, Unnamed Item, Connectivity-splitting models for survivable network design, Modifying edges of a network to obtain short subgraphs, Approximating minimum-power edge-covers and 2,3-connectivity, Approximating Source Location and Star Survivable Network Problems, Approximating fault-tolerant group-Steiner problems, Recent results on approximating the Steiner tree problem and its generalizations, Algorithms for a network design problem with crossing supermodular demands, Designing Hypergraph Layouts to GMPLS Routing Strategies, An efficient approximation algorithm for the survivable network design problem, Socially fair network design via iterative rounding, Approximation algorithms for vertex-connectivity augmentation on the cycle, Approximation algorithm for the group Steiner network problem, Algorithms for a multi-level network optimization problem, Reducing Path TSP to TSP, Approximating minimum size \{1,2\}-connected networks, A primal-dual approximation algorithm for the survivable network design problem in hypergraphs, Approximability of capacitated network design, On fixed cost \(k\)-flow problems, Flexible graph connectivity
