An Improved Algorithm for Fixed-Hub Single Allocation Problems

Dong Dong Ge, Zi Zhuo Wang, Lai Wei, Jia Wei Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


This paper discusses the fixed-hub single allocation problem (FHSAP). In this problem, a network consists of hub nodes and terminal nodes. Hubs are fixed and fully connected; each terminal node is assigned to a single hub which routes all its traffic. The goal is to minimize the cost of routing the traffic in the network. In this paper, we propose a new linear programming (LP) relaxation for this problem by incorporating a set of validity constraints into the classical formulations by Ernst and Krishnamoorthy (Locat Sci 4:139–154, Ann Op Res 86:141–159). A geometric rounding algorithm is then used to obtain an integral solution from the fractional solution. We show that by incorporating the validity constraints, the strengthened LP often provides much tighter upper bounds than the previous methods with a little more computational effort and the solution obtained often has a much smaller gap with the optimal solution. We also formulate a robust version of the FHSAP and show that it can guard against data uncertainty with little costs.

Original languageEnglish (US)
Pages (from-to)319-332
Number of pages14
JournalJournal of the Operations Research Society of China
Issue number3
StatePublished - Sep 1 2017

Bibliographical note

Funding Information:
The first author was supported by the National Natural Science Foundation of China (No. 11471205).

Publisher Copyright:
© 2016, Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg.


  • Hub location
  • Linear programming
  • Network design
  • Worst-case analysis


Dive into the research topics of 'An Improved Algorithm for Fixed-Hub Single Allocation Problems'. Together they form a unique fingerprint.

Cite this