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

Resumo

No problema de centros dos p-terminais são dados um espaço métrico (V, d) e um conjunto D ⊆ V² que representa demandas de fluxo. O objetivo é selecionar um subconjunto de V de tamanho p, denominado terminais, e associar cada demanda uv ∈ D a um terminal w, de forma a minimizar o maior custo de percurso entre uma origem u, o terminal associado w e o destino v. Embora os problemas de alocação de terminais componham uma área bastante ativa nos últimos anos, ainda há poucos trabalhos de aproximação. Para o problema de centros dos p-terminais, nós verificamos um limitante inferior de 2 para o fator e obtemos um primeiro algoritmo de aproximação, com fator 3.

 

Referências

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.