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.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
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