Title: A Linear Programming-Based Algorithm for the Fixed-Hub Single Allocation
Problem

Abstract: This paper discusses the fixed-hub single allocation problem. In the
model hubs are fixed and fully connected; and each terminal node is connected to a
single hub which routes all its traffic. The goal is to minimize the cost of
routing the traffic in the network. This paper  presents a linear
programming-based algorithm that delivers both high quality solutions and a
theoretical worst case bound. Our algorithm is based on a new randomized rounding
method, which might be of interest on its own. (This is a joint work with Dongdong
Ge and Yinyu Ye).