Approximation algorithm for cycle-star hub network design problems and cycle-metric labeling problems
From MaRDI portal
Publication:2980928
Abstract: We consider a single allocation hub-and-spoke network design problem which allocates each non-hub node to exactly one of given hub nodes so as to minimize the total transportation cost. This paper deals with a case in which the hubs are located in a cycle, which is called a cycle-star hub network design problem. The problem is essentially equivalent to a cycle-metric labeling problem. The problem is useful in the design of networks in telecommunications and airline transportation systems.We propose a -approximation algorithm where denotes the number of hub nodes. Our algorithm solves a linear relaxation problem and employs a dependent rounding procedure. We analyze our algorithm by approximating a given cycle-metric matrix by a convex combination of Monge matrices.
Recommendations
- Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
- Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
- Algorithm for single allocation problem on hub-and-spoke networks in 2-dimensional plane
- Exact and heuristic approaches for the cycle hub location problem
- Approximation algorithms for median hub location problems
Cites work
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- A Monge property for the \(d\)-dimensional transportation problem
- A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
- A linear program for the two-hub location problem
- A quadratic integer program for the location of interacting hub facilities
- A study of the quadratic semi-assignment polytope
- A tabu-search based heuristic for the hub covering problem over incomplete hub networks
- Algorithm for single allocation problem on hub-and-spoke networks in 2-dimensional plane
- An improved Benders decomposition algorithm for the tree of hubs location problem
- 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
- Exact and heuristic approaches for the cycle hub location problem
- Hub Arc Location Problems: Part II—Formulations and Optimal Algorithms
- Hub arc location problems: I. Introduction and results
- Network hub location problems: The state of the art
- Perspectives of Monge properties in optimization
- Solving the hub location problem in a star–star network
- Star \(p\)-hub center problem and star \(p\)-hub median problem with bounded path lengths
- Star \(p\)-hub median problem with modular arc capacities
- The Hardness of Metric Labeling
- The single allocation problem in the interacting three-hub network
- The tree of hubs location problem
- Tight bounds from a path based formulation for the tree of hub location problem
Cited in
(3)- 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
- A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case
This page was built for publication: Approximation algorithm for cycle-star hub network design problems and cycle-metric labeling problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2980928)
