𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The single allocation problem in the interacting three-hub network

✍ Scribed by Sohn, Jinhyeon; Park, Sungsoo

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
112 KB
Volume
35
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the single allocation problem in the interacting three-hub network with fixed hub locations. In the single allocation hub network, the hubs are fully interconnected and each nonhub node has to be connected to exactly one of the hubs. The flows between each pair of nodes are sent using the hubs as intermediate switching points. The problem is to find an optimal allocation of nonhub nodes to the hubs which minimizes the total flow cost. We show that the single allocation problem is NP-hard as soon as the number of hubs is three, although the problem in a two-hub system has polynomial time algorithms. This paper provides a mixed integer formulation of the problem and considers the polyhedral properties of it. The formulation can also be used for the single allocation problem with fixed costs for opening links, the threeterminal cut problem, and the three-processor distribution problem. Computational experiences are reported for data given in the literature and randomly generated problems.

πŸ“œ SIMILAR VOLUMES

Solving the hub location problem in a st
Solving the hub location problem in a star–star network
✍ Martine LabbΓ©; Hande Yaman πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 273 KB πŸ‘ 1 views

## Abstract We consider the problem of locating hubs and assigning terminals to hubs for a telecommunication network. The hubs are directly connected to a central node and each terminal node is directly connected to a hub node. The aim is to minimize the cost of locating hubs, assigning terminals a

Cost allocation in networks: The bulk su
Cost allocation in networks: The bulk supplier problem
✍ A. Claus; D. J. Kleitman πŸ“‚ Article πŸ“… 1974 πŸ› John Wiley and Sons 🌐 English βš– 994 KB

## Abstract We consider the cost allocation problem faced by a large scale supplier (the telephone company) who rents telephone circuits to its customers. A number of possible allocation rate structures are analyzed, as are some of the criteria that they may be measured by. Finally, we draw conclus