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

DOI10.1007/978-3-319-53925-6_31zbMATH Open1485.68313OpenAlexW2566210220MaRDI 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

• 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)