Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems

DOI10.1016/j.dam.2008.11.016zbMath1164.90019OpenAlexW1968036138MaRDI QIDQ1026110

Tomomi Matsui, Masaru Iwasa, Hiroo Saito

Publication date: 24 June 2009

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

Full work available at URL: https://doi.org/10.1016/j.dam.2008.11.016

zbMATH Keywords

approximation algorithmhub locationmetric labelingdependent rounding

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

Robust optimization approach to capacitated single and multiple allocation hub location problems, Improved hardness and approximation results for single allocation hub location problems, Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems, Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs, A parameterized approximation algorithm for the multiple allocation \(k\)-hub center, Approximation algorithms for median hub location problems, A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case, Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems, Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs, Improved hardness and approximation results for single allocation hub location

Cites Work

• Unnamed Item
• Adapting polyhedral properties from facility to hub location problems
• A study of the quadratic semi-assignment polytope
• A quadratic integer program for the location of interacting hub facilities
• A linear program for the two-hub location problem
• On dependent randomized rounding algorithms
• Integer programming formulations of discrete hub location problems
• A branch and cut algorithm for hub location problems with single assignment
• Perspectives of Monge properties in optimization
• Projecting the flow variables for hub location problems
• Convex quadratic and semidefinite programming relaxations in scheduling
• Approximation algorithms for classification problems with pairwise relationships
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• The single allocation problem in the interacting three-hub network
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• The Hardness of Metric Labeling