A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case
From MaRDI portal
Publication:6130232
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06)
Abstract: Transportation networks frequently employ hub-and-spoke network architectures to route flows between many origin and destination pairs. Hub facilities work as switching points for flows in large networks. In this study, we deal with a problem, called the single allocation hub-and-spoke network design problem. In the problem, the goal is to allocate each non-hub node to exactly one of given hub nodes so as to minimize the total transportation cost. The problem is essentially equivalent to another combinatorial optimization problem, called the metric labeling problem. The metric labeling problem was first introduced by Kleinberg and Tardos in 2002, motivated by application to segmentation problems in computer vision and related areas. In this study, we deal with the case where the set of hubs forms a star, which arises especially in telecommunication networks. We propose a polynomial-time randomized approximation algorithm for the problem, whose approximation ratio is less than 5.281. Our algorithms solve a linear relaxation problem and apply dependent rounding procedures.
Recommendations
- Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
- Approximation algorithm for cycle-star hub network design problems and cycle-metric labeling problems
- Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
- Algorithm for single allocation problem on hub-and-spoke networks in 2-dimensional plane
- Approximation algorithms for median hub location problems
Cites work
- scientific article; zbMATH DE number 1775400 (Why is no real title available?)
- A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
- A Monge property for the \(d\)-dimensional transportation problem
- A linear program for the two-hub location problem
- A tight bound on approximating arbitrary metrics by tree metrics
- Algorithm for single allocation problem on hub-and-spoke networks in 2-dimensional plane
- Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
- Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
- Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
- Minimum 0-extensions of graph metrics
- On approximating planar metrics by tree metrics.
- Perspectives of Monge properties in optimization
- Solving the hub location problem in a star–star network
- The Complexity of Multiterminal Cuts
- The Hardness of Metric Labeling
- The single allocation problem in the interacting three-hub network
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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6130232)
