Approximation algorithm for cycle-star hub network design problems and cycle-metric labeling problems

DOI10.1007/978-3-319-53925-6_31zbMATH Open1485.68313arXiv1612.02990OpenAlexW2566210220MaRDI QIDQ2980928FDOQ2980928

Authors: Yuko Kuroki, Tomomi Matsui 

Publication date: 5 May 2017

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

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 $2(1-1/h)$-approximation algorithm where $h$ 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.

Full work available at URL: https://arxiv.org/abs/1612.02990

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Approximation algorithms (68W25) Communication networks in operations research (90B18)

Cites Work

• The tree of hubs location problem
• A quadratic integer program for the location of interacting hub facilities
• An improved Benders decomposition algorithm for the tree of hubs location problem
• Network hub location problems: The state of the art
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• A tabu-search based heuristic for the hub covering problem over incomplete hub networks
• Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
• Hub arc location problems: I. Introduction and results
• Hub Arc Location Problems: Part II—Formulations and Optimal Algorithms
• The single allocation problem in the interacting three-hub network
• Tight bounds from a path based formulation for the tree of hub location problem
• Perspectives of Monge properties in optimization
• Exact and heuristic approaches for the cycle hub location problem
• Solving the hub location problem in a star–star network
• A study of the quadratic semi-assignment polytope
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Star \(p\)-hub center problem and star \(p\)-hub median problem with bounded path lengths
• A Monge property for the \(d\)-dimensional transportation problem
• Star \(p\)-hub median problem with modular arc capacities
• Approximation algorithms for classification problems with pairwise relationships
• A linear program for the two-hub location problem
• The Hardness of Metric Labeling
• Algorithm for single allocation problem on hub-and-spoke networks in 2-dimensional plane

Cited In (2)

• 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

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)