Provisioning a virtual private network: a network design problem for multicommodity flow

DOI10.1145/380752.380830MaRDI QIDQ5175994zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, Amit Kumar, Rajeev Rastogi, Bülent Yener, 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

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

Recommendations

• Automata, Languages and Programming
• Provisioning virtual private networks under traffic uncertainty
• Virtual private network design
• New Approaches for Virtual Private Network Design
• An improved approximation algorithm for virtual private network design

Cites work

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

Cited in

(68)

• Approximation algorithms for connected facility location problems
• A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees
• Black-box reductions for cost-sharing mechanism design
• The asymmetric VPN tree problem: polyhedral results and Branch-and-Cut
• A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation
• A note on hierarchical hubbing for a generalization of the VPN problem
• The General Steiner Tree-Star problem.
• General network design: a unified view of combined location and network design problems
• Connected facility location via random facility sampling and core detouring
• On the approximability of robust network design
• A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design
• Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty
• Electrical flows over spanning trees
• Exact algorithms for budgeted prize-collecting covering subgraph problems
• Generalized hose uncertainty in single-commodity robust network design
• The robust network loading problem with dynamic routing
• Resource optimization algorithms for virtual private networks using the hose model
• New discoveries of domination between traffic matrices
• Data locality and replica aware virtual cluster embeddings
• A PTAS for the geometric connected facility location problem
• Network design with a discrete set of traffic matrices
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Meet and merge: approximation algorithms for confluent flows
• Towards optimizing the deployment of optical access networks
• An automated network generation procedure for routing of unmanned aerial vehicles (UAVs) in a GIS environment
• On the robustness of potential-based flow networks
• Approximate the lower-bounded connected facility location problem
• scientific article; zbMATH DE number 1717209 (Why is no real title available?)
• From uncertainty to nonlinearity: solving virtual private network via single-sink buy-at-bulk
• An improved approximation algorithm for virtual private network design
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees (extended abstract)
• Approximate robust optimization for the connected facility location problem
• Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
• Combinatorial approximation algorithms for buy-at-bulk connected facility location problems
• Benders decomposition of the passive optical network design problem
• Provisioning virtual private networks under traffic uncertainty
• Provisioning a Virtual Private Network Under the Presence of Non-communicating Groups
• LP-based approximation algorithms for facility location in buy-at-bulk network design
• New Approaches for Virtual Private Network Design
• Hardness of robust network design
• scientific article; zbMATH DE number 1532269 (Why is no real title available?)
• A comparison of routing sets for robust network design
• Approximation algorithms for a combined facility location buy-at-bulk network design problem
• Single-sink fractionally subadditive network design
• Affine recourse for the robust network design problem: between static and dynamic routing
• The VPN conjecture is true
• Virtual private network design
• Linear programming models for traffic engineering in 100\% survivable networks under combined IS-IS/OSPF and MPLS-TE
• Virtual private network design over the first Chvátal closure
• Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
• Automata, Languages and Programming
• Black-box reductions for cost-sharing mechanism design
• Affine routing for robust network design
• Minimizing recovery cost of network optimization problems
• Static and dynamic routing under disjoint dominant extreme demands
• Branch-and-cut-and-price for capacitated connected facility location
• LP-based approximation algorithms for facility location in buy-at-bulk network design
• Robust algorithms for TSP and Steiner tree
• A polynomial-time exact algorithm for the connected k-facility location problem on trees
• The ordered median tree location problem
• MIP models for connected facility location: a theoretical and computational study
• Experiments on virtual private network design with concave capacity costs
• On the connected minimum sum of radii problem
• Design of trees in the hose model: the balanced case
• Multi-path routing versus tree routing for VPN bandwidth provisioning in the hose model
• A short proof of the VPN tree routing conjecture on ring networks
• Approximability and inapproximability of the minimum certificate dispersal problem

This page was built for publication: Provisioning a virtual private network: a network design problem for multicommodity flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175994)