A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case
Publication:6130232
DOI10.1016/J.DAM.2024.02.011arXiv1803.06114OpenAlexW4392214167MaRDI QIDQ6130232
Publication date: 2 April 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1803.06114
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
- A linear program for the two-hub location problem
- Minimum 0-extensions of graph metrics
- On approximating planar metrics by tree metrics.
- A Monge property for the \(d\)-dimensional transportation problem
- Perspectives of Monge properties in optimization
- Algorithm for Single Allocation Problem on Hub-and-Spoke Networks in 2-Dimensional Plane
- Approximation algorithms for classification problems with pairwise relationships
- The Complexity of Multiterminal Cuts
- Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
- The single allocation problem in the interacting three-hub network
- A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
- The Hardness of Metric Labeling
- Solving the hub location problem in a star–star network
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case
