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, Hiroo Saito, Masaru Iwasa

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

Robust optimization approach to capacitated single and multiple allocation hub location problems, Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems

Cites Work

• Unnamed Item
• 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
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• The Hardness of Metric Labeling