Hardness of robust network design

DOI10.1002/NET.20165zbMATH Open1119.90005OpenAlexW2788302603MaRDI QIDQ3593369FDOQ3593369

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

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

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)

Cites Work

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

Cited In (33)

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

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)