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

DOI10.1016/j.dam.2008.11.016zbMath1164.90019MaRDI 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 algorithm; hub location; metric labeling; dependent rounding

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90B10: Deterministic network models in operations research

90B80: Discrete location and assignment

68W25: Approximation algorithms

Related Items

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

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