Approximability of unsplittable shortest path routing problems

DOI10.1002/NET.20303MaRDI QIDQ3057101zbMATH OpenOpenAlexFDO

Authors Andreas Bley

Publication date 24 November 2010

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20303

zbMATH Keywords

approximationcomputational complexityshortest path routingunsplittable flow

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Communication networks in operations research (90B18)

Recommendations

• On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem
• Approximation algorithms for single-source unsplittable flow
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• On the single-source unsplittable flow problem
• Approximating the single source unsplittable min-cost flow problem

Cites work

• A constant factor approximation for the single sink edge installation problems
• A General Approximation Technique for Constrained Forest Problems
• A genetic algorithm for the weight setting problem in OSPF routing
• A hybrid genetic algorithm for the weight setting problem in OSPF/IS‐IS routing
• A tight bound on approximating arbitrary metrics by tree metrics
• An Integer Programming Algorithm for Routing Optimization in IP Networks
• Approximating the single source unsplittable min-cost flow problem
• Compatible weights and valid cycles in non-spanning OSPF routing patterns
• Cost-Distance: Two Metric Network Design
• Design networks with bounded pairwise distance
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303557 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• scientific article; zbMATH DE number 2086941 (Why is no real title available?)
• scientific article; zbMATH DE number 6472639 (Why is no real title available?)
• Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths
• Increasing internet capacity using local search
• Internet Routing and Related Topology Issues
• Multi-hour design of survivable classical IP networks
• On non-uniform multicommodity buy-at-bulk network design
• On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem
• On the single-source unsplittable flow problem
• Optimization of Internet Protocol network design and routing
• Routing and capacity optimization for IP networks
• Simpler and better approximation algorithms for network design
• The Ring Loading Problem

Cited in

(13)

• Counterexamples to the uniform shortest path routing conjecture for vertex-transitive graphs
• The subdivision-constrained routing requests problem
• Optimization of OSPF routing in IP networks
• An Integer Programming Algorithm for Routing Optimization in IP Networks
• On the union of intermediate nodes of shortest paths
• On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem
• New Sharpness Properties, Algorithms and Complexity Bounds for Partitioning Shortest Path Procedures
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• An integer programming algorithm for routing optimization in IP networks
• Metaheuristics for solving the biobjective single‐path multicommodity communication flow problem
• An enhanced Benders decomposition method for unique shortest path routing
• Routing and capacity optimization for IP networks
• A multi-start variable neighborhood search for solving the single path multicommodity flow problem

This page was built for publication: Approximability of unsplittable shortest path routing problems

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