A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case

DOI10.1016/J.DAM.2024.02.011arXiv1803.06114OpenAlexW4392214167MaRDI QIDQ6130232FDOQ6130232

Authors: Yuko Kuroki, Tomomi Matsui 

Publication date: 2 April 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

combinatorial optimizationtransportationfacilities planning and design

Mathematics Subject Classification ID

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)

Cites Work

• The Complexity of Multiterminal Cuts
• Title not available (Why is that?)
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
• The single allocation problem in the interacting three-hub network
• Perspectives of Monge properties in optimization
• Solving the hub location problem in a star–star network
• A Monge property for the \(d\)-dimensional transportation problem
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• A linear program for the two-hub location problem
• Minimum 0-extensions of graph metrics
• On approximating planar metrics by tree metrics.
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• The Hardness of Metric Labeling
• 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

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)