Uma Aproximação para o Problema de Alocação de Terminais

• Lehilton L. C. Pedrosa UNICAMP
• Vinícius F. dos Santos UFMG
• Rafael C. S. Schouery UNICAMP

DOI: https://doi.org/10.5753/etc.2016.9834

Abstract

In the center p-hub problem, we are given a metric space (V, d) and a set D ⊆ V², that represents flow demands. The objective is to select a subset of V of size p, which are called hubs, and assign each demand uv to a terminal w, minimizing the maximum distance of traveling from origin u, hub w, and destination v. Although hub location problems comprise a very active area, there are few works on approximation. For the center p-hub problem, we notice that there is a lower bound of 2, and obtain the first approximation, that achieves factor 3.

 

References

Farahani, R. Z., Hekmatfar, M., Arabani, A. B., and Nikbakhsh, E. (2013). Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, 64(4):1096–1109.

Hochbaum, D. S. and Shmoys, D. B. (1986). A Unified Approach to Approximation Algorithms for Bottleneck Problems. Journal of the ACM, 33(3):533–550.

Iwasa, M., Saito, H., and Matsui, T. (2009). Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems. Discrete Applied Mathematics, 157(9):2078–2088.

Liang, H. (2013). The hardness and approximation of the star-hub center problem. Operations Research Letters, 41(2):138–141.

O’Kelly, M. E. (1986). The Location of Interacting Hub Facilities. Transportation Science, 20(2):92–106.

Sohn, J. and Park, S. (1997). A linear program for the two-hub location problem. European Journal of Operational Research, 100(3):617–622.

Yaman, H. and Elloumi, S. (2012). Star p-hub center problem and star p-hub median problem with bounded path lengths. Computers & Operations Research, 39(11):2725–2732.