Hardness of robust network design

DOI10.1002/NET.20165MaRDI QIDQ3593369zbMATH OpenOpenAlexFDO

Authors

Publication date 20 July 2007

Published in Networks (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2108/12068

zbMATH Keywords

robust optimizationnetwork designsingle-source hose model

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Recommendations

• Robust network optimization under polyhedral demand uncertainty is \(NP\)-hard
• Approximability of robust network design
• On the approximability of robust network design
• On the approximability of some network design problems
• On the approximability of some network design problems

Cites work

• Automata, Languages and Programming
• Geometric algorithms and combinatorial optimization
• On the power of unique 2-prover 1-round games
• Provisioning a virtual private network: a network design problem for multicommodity flow
• Simpler and better approximation algorithms for network design
• Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks

Cited in

(32)

• An approach to robust network design in telecommunications
• Robust delay-constrained routing in telecommunications
• On the complexity of resilient network design
• Robust network design: formulations, valid inequalities, and computations
• On total traffic domination in non-complete graphs
• Static and dynamic routing under disjoint dominant extreme demands
• Competitive and deterministic embeddings of virtual networks
• Single-commodity robust network design with finite and hose demand sets
• A capacitated hub location problem under hose demand uncertainty
• New discoveries of domination between traffic matrices
• Robust multiobjective optimization with application to Internet routing
• Multipolar robust optimization
• A distributed method for optimal capacity reservation
• Linear programming models for traffic engineering in 100\% survivable networks under combined IS-IS/OSPF and MPLS-TE
• Vertex sparsification in trees
• On improving optimal oblivious routing
• Robust network optimization under polyhedral demand uncertainty is \(NP\)-hard
• Design of trees in the hose model: the balanced case
• Network design with a discrete set of traffic matrices
• Affine routing for robust network design
• Further contributions to network optimization
• Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard
• Telecommunications network design: Technology impacts and future directions
• On the approximability of robust network design
• A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation
• Approximability of robust network design
• Affine recourse for the robust network design problem: between static and dynamic routing
• scientific article; zbMATH DE number 2161745 (Why is no real title available?)
• Robust routing and optimal partitioning of a traffic demand polytope
• On 2-stage robust LP with RHS uncertainty: complexity results and applications
• A comparison of routing sets for robust network design
• The robust network loading problem with dynamic routing

This page was built for publication: Hardness of robust network design

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