Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
From MaRDI portal
Publication:1026110
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
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
