Improved approximation algorithms for network design problems

No abstract is available for this paper.

• Publication year

  1994

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  1994-01-23

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Preserving and Increasing Local Edge-Connectivity in Mixed Graphs

  1995cited by this paper
• A scaling technique for better network design

  1994influential reference
• Blocking Small Cuts in a Network, and Related Problems

  1993influential reference
• Survivable networks, linear programming relaxations and the parsimonious property

  1993cited by this paper
• A primal-dual approximation algorithm for generalized steiner network problems

  1993cited by this paper
• An E cient Approximation Algorithmfor the Survivable Network Design Problem

  1993influential reference
• On the design of approximation algorithms for a class of graph problems

  1993cited by this paper
• A general approximation technique for constrained forest problems

  1992cited by this paper
• When cycles collapse: A general approximation technique for constrained two-connectivity problems

  1992cited by this paper
• When trees collide: an approximation algorithm for the generalized Steiner problem on networks

  1991influential reference
• A new algorithm for minimizing convex functions over convex sets

  1989cited by this paper
• Geometric Algorithms and Combinatorial Optimization

  1988cited by this paper
• Network Design and Transportation Planning: Models and Algorithms

  1984cited by this paper
• On the structure of all minimum cuts in a network and applications

  1982influential reference

• Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree

  2025cites this paper
• Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures

  2025cites this paper
• Streaming Algorithms for Network Design

  2025influential citation
• Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique

  2025cites this paper
• A New Approach for Approximating Directed Rooted Networks

  2024cites this paper
• Model-Agnostic Approximation of Constrained Forest Problems

  2024cites this paper
• Improved Approximation Algorithms for Flexible Graph Connectivity and Capacitated Network Design

  2024cites this paper
• Streaming Algorithms for Connectivity Augmentation

  2024influential citation
• Approximation Algorithms for Network Design in Non-Uniform Fault Models

  2024cites this paper
• Correlation Clustering and Two-Edge-Connected Augmentation for Planar Graphs

  2023cites this paper
• A Global Analysis of the Primal-Dual Method for Edge Augmentation Problems

  2023influential citation
• Improved approximation algorithms for some capacitated k edge connectivity problems

  2023cites this paper
• An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem

  2023cites this paper
• Approximation Algorithms for Steiner Tree Augmentation Problems

  2022cites this paper
• Approximation algorithms for flexible graph connectivity

  2022cites this paper
• Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

  2022cites this paper
• Better-than-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{4}{3}$$\end{document}43-approximations for leaf-to-l

  2022cites this paper
• Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions

  2022influential citation
• Survivable Network Design Revisited: Group-Connectivity

  2022cites this paper
• New and improved approximation algorithms for Steiner Tree Augmentation Problems

  2022cites this paper
• Augmentation based Approximation Algorithms for Flexible Network Design

  2022cites this paper
• using pairs of failure-disjoint paths.

  2022cites this paper
• Approximating Flexible Graph Connectivity via Räcke Tree based Rounding

  2022cites this paper
• A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning Subgraph

  2022cites this paper
• Approximation Algorithms for Connectivity Augmentation Problems

  2022cites this paper
• A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation

  2022cites this paper
• Node connectivity augmentation via iterative randomized rounding

  2021cites this paper
• A Better-Than-2 Approximation for Weighted Tree Augmentation

  2021cites this paper
• Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle

  2021cites this paper
• Bridging the gap between tree and connectivity augmentation: unified and stronger approaches

  2020cites this paper
• Distributed Network Design

  2020cites this paper
• Approximation Algorithms for Traveling Salesman Problems

  2020cites this paper
• A spectral approach to network design

  2020cites this paper
• Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings

  2020cites this paper
• Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph

  2019cites this paper
• Approximation of Steiner forest via the bidirected cut relaxation

  2019cites this paper
• Approximation Algorithms for Process Systems Engineering

  2019cites this paper
• Network Design for s-t Effective Resistance

  2019cites this paper
• D S ] 2 2 Ja n 20 19 A ( 4 + ǫ )-approximation for k-connected subgraphs

  2019cites this paper
• Reducing path TSP to TSP

  2019cites this paper
• A $(4+\epsilon)$-approximation for $k$-connected subgraphs

  2019cites this paper
• Flexible Graph Connectivity

  2019influential citation
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs

  2019cites this paper
• Approximating k-Connected m-Dominating Sets

  2019cites this paper
• On the Cycle Augmentation Problem: Hardness and Approximation Algorithms

  2019cites this paper
• Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree

  2019cites this paper
• Designing WAN Topologies Under Redundancy Constraints 14

  2018cites this paper
• The Complexity of Network Design for s-t Eff ective Resistance

  2018cites this paper
• A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs

  2018cites this paper
• Optimization Everywhere: Convex, Combinatorial, and Economic

  2018cites this paper
• Improved approximation for tree augmentation: saving by rewiring

  2018cites this paper
• Complexity of minimum irreducible infeasible subsystem covers for flow networks

  2018cites this paper
• LP-Relaxations for Tree Augmentation

  2018cites this paper
• Algorithm engineering in geometric network planning and data mining

  2018cites this paper
• Erratum: Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies

  2018cites this paper
• A Computational Approach to Organizational Structure

  2018cites this paper
• Activation Network Design Problems

  2018cites this paper
• Greedy Algorithms for Online Survivable Network Design

  2018cites this paper
• Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs

  2018cites this paper
• A Note on Iterated Rounding for the Survivable Network Design Problem

  2018cites this paper
• Title A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraphs (New Developments of Theory of Computation and Algorithms)

  2018influential citation
• Node-Connectivity Survivable Network Problems

  2018cites this paper
• Optimization-based Models for Pruning the Design-space for Processors

  2017cites this paper
• Discrete and robust optimization approaches to network design with compression and virtual network embedding

  2017cites this paper
• On the Tree Augmentation Problem 1

  2017cites this paper
• A 3/2-Approximation Algorithm for Tree Augmentation via Chvátal-Gomory Cuts

  2017cites this paper
• Improved Inapproximability Results for Steiner Tree via Long Code Based Reductions

  2017cites this paper
• Fast distributed approximation for TAP and 2-edge-connectivity

  2017cites this paper
• 61 : 2 On the Tree Augmentation Problem

  2017cites this paper
• Improved Approximation Algorithms for Minimum Cost Node-Connectivity Augmentation Problems

  2017cites this paper
• Online Constrained Forest and Prize-Collecting Network Design

  2017cites this paper
• Towards New Bounds for the 2-Edge Connected Spanning Subgraph Problem

  2017cites this paper
• University of Birmingham A tight algorithm for Strongly Connected Steiner Subgraph on two terminals with demands

  2017cites this paper
• Improved Inapproximability Results for Steiner Tree via Long Code Based Reductions

  2017cites this paper
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs

  2017cites this paper
• The multi-budgeted and weighted bounded degree metric Steiner network problem

  2017cites this paper
• A Note on the Tree Augmentation Problem

  2017cites this paper
• Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree

  2017cites this paper
• On the Tree Augmentation Problem

  2017cites this paper
• Brief Announcement: Distributed Approximation for Tree Augmentation

  2017cites this paper
• Surviving in Directed Graphs: A Polylogarithmic Approximation for Two-Connected Directed Steiner Tree

  2016cites this paper
• Improved Approximation for Weighted Tree Augmentation with Bounded Costs

  2016cites this paper
• A note on the Survivable Network Design Problem

  2016cites this paper
• Optimization Models for Three On-Chip Network Problems

  2016cites this paper
• Optimization problems in network mechanism design

  2016cites this paper
• Fast Approximation Algorithms for the Generalized Survivable Network Design Problem

  2016cites this paper
• Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems

  2016cites this paper
• Network Design with Facility Location Approximation and Exact Techniques

  2015cites this paper
• A 1.75 LP approximation for the Tree Augmentation Problem

  2015cites this paper
• Approximation Algorithms for Multi-budgeted Network Design Problems

  2015cites this paper
• The parsimonious property of cut covering problems and its applications

  2015influential citation
• A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2

  2015cites this paper
• Graph Algorithms: Network Inference and Planar Graph Optimization. (Algorithmes des Graphes: Inférence des Réseaux et Optimisation dans les Graphes Planaires)

  2015cites this paper
• On Survivable Set Connectivity

  2015cites this paper
• Fractional routing using pairs of failure-disjoint paths

  2014influential citation
• Covering deficient trees

  2014cites this paper
• An LP 7 / 4-approximation for the Tree Augmentation Problem

  2014cites this paper
• Incremental network design with shortest paths

  2014cites this paper
• ON HALF-INTEGRALITY OF NETWORK SYNTHESIS PROBLEM

  2014cites this paper
• A Bound on the Expected Optimality of Random Feasible Solutions to Combinatorial Optimization Problems

  2014cites this paper