Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems

DOI10.7155/jgaa.00485zbMath1405.05176OpenAlexW2912702020MaRDI QIDQ4622772

Yuko Kuroki, Tomomi Matsui

Publication date: 14 February 2019

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00485

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Deterministic network models in operations research (90B10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

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

Cites Work

• A tabu-search based heuristic for the hub covering problem over incomplete hub networks
• Tight bounds from a path based formulation for the tree of hub location problem
• A study of the quadratic semi-assignment polytope
• Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
• The tree of hubs location problem
• A quadratic integer program for the location of interacting hub facilities
• A linear program for the two-hub location problem
• Exact and heuristic approaches for the cycle hub location 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
• Perspectives of Monge properties in optimization
• An improved Benders decomposition algorithm for the tree of hubs location problem
• Star \(p\)-hub median problem with modular arc capacities
• Network hub location problems: The state of the art
• Algorithm for Single Allocation Problem on Hub-and-Spoke Networks in 2-Dimensional Plane
• Hub Arc Location Problems: Part I—Introduction and Results
• Hub Arc Location Problems: Part II—Formulations and Optimal Algorithms
• Approximation algorithms for classification problems with pairwise relationships
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• The single allocation problem in the interacting three-hub network
• The Hardness of Metric Labeling
• Solving the hub location problem in a star–star network
• A tight bound on approximating arbitrary metrics by tree metrics