Provisioning a virtual private network

DOI10.1145/380752.380830zbMath1323.68014OpenAlexW2094410510MaRDI QIDQ5175994

Bülent Yener, Amit Kumar, Rajeev Rastogi, Anupam Gupta, Jon M. Kleinberg

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380830

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (55)

Approximate robust optimization for the connected facility location problem ⋮ A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design ⋮ The robust network loading problem with dynamic routing ⋮ Combinatorial approximation algorithms for buy-at-bulk connected facility location problems ⋮ Exact algorithms for budgeted prize-collecting covering subgraph problems ⋮ Benders decomposition of the passive optical network design problem ⋮ An automated network generation procedure for routing of unmanned aerial vehicles (UAVs) in a GIS environment ⋮ Design of trees in the hose model: the balanced case ⋮ New discoveries of domination between traffic matrices ⋮ Affine recourse for the robust network design problem: Between static and dynamic routing ⋮ Data locality and replica aware virtual cluster embeddings ⋮ A PTAS for the geometric connected facility location problem ⋮ General network design: a unified view of combined location and network design problems ⋮ Generalized hose uncertainty in single-commodity robust network design ⋮ Affine routing for robust network design ⋮ A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract) ⋮ Minimizing recovery cost of network optimization problems ⋮ Static and dynamic routing under disjoint dominant extreme demands ⋮ On the robustness of potential-based flow networks ⋮ Dynamic vs. oblivious routing in network design ⋮ Approximate the lower-bounded connected facility location problem ⋮ Connected facility location via random facility sampling and core detouring ⋮ Network design with a discrete set of traffic matrices ⋮ A comparison of routing sets for robust network design ⋮ Branch-and-cut-and-price for capacitated connected facility location ⋮ LP-based approximation algorithms for facility location in buy-at-bulk network design ⋮ Black-box reductions for cost-sharing mechanism design ⋮ A short proof of the VPN tree routing conjecture on ring networks ⋮ The asymmetric VPN tree problem: polyhedral results and Branch-and-Cut ⋮ Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems ⋮ Approximation Algorithms for Single and Multi-Commodity Connected Facility Location ⋮ A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation ⋮ On the approximability of robust network design ⋮ Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design Problem ⋮ Linear programming models for traffic engineering in 100\% survivable networks under combined IS-IS/OSPF and MPLS-TE ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ MIP models for connected facility location: a theoretical and computational study ⋮ Hedging uncertainty: approximation algorithms for stochastic optimization problems ⋮ Meet and merge: approximation algorithms for confluent flows ⋮ Hardness of robust network design ⋮ Approximability and inapproximability of the minimum certificate dispersal problem ⋮ A note on hierarchical hubbing for a generalization of the VPN problem ⋮ Experiments on virtual private network design with concave capacity costs ⋮ Towards optimizing the deployment of optical access networks ⋮ Unnamed Item ⋮ Approximation algorithms for connected facility location problems ⋮ A 6.55 factor primal-dual approximation algorithm for the connected facility location problem ⋮ Provisioning virtual private networks under traffic uncertainty ⋮ Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty ⋮ Virtual private network design over the first Chvátal closure ⋮ Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem ⋮ Electrical flows over spanning trees ⋮ The General Steiner Tree-Star problem. ⋮ Unnamed Item

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Provisioning a virtual private network