A Constant-Factor Approximation for the Generalized Cable-Trench Problem
Resumo
In the Cable-Trench Problem (CTP), the objective is to find a rooted spanning tree of a weighted graph that minimizes the length of the tree, scaled by a non-negative factor , plus the sum of all shortest-path lengths from the root, scaled by another non-negative factor. This is an intermediate optimization problem between the Single-Destination Shortest Path Problem and the Minimum Spanning Tree Problem. In this extended abstract, we consider the Generalized CTP (GCTP), in which some vertices need not be connected to the root, but may serve as cost-saving merging points; this variant also generalizes the Steiner Tree Problem. We present an 8.599-approximation algorithm for GCTP. Before this paper, no constant approximation for the standard CTP was known.
Referências
Nielsen, R. H., Riaz, M. T., Pedersen, J. M., and Madsen, O. B. (2008). On the potential of using the cable trench problem in planning of ict access networks. In 2008 50th International Symposium ELMAR, volume 2, pages 585–588. IEEE.
Rocha, U., Ramos, N., Melo, L., Benedito, M., Silva, A., Cano, R., Miyazawa, F., and Xavier, E. (2017). Abordagens heurısticas para o p-cabo-trincheira com localizacao de instalacoes. In 2o Encontro de Teoria da Computacao (ETC), volume 2. SBC.
Rocha, U. A. C. (2018). Heuristic techniques for large-scale instances of the cable- trench problem. Dissertacao de mestrado, Instituto de Computacao.
Vasko, F. J., Barbieri, R. S., Rieksts, B. Q., Reitmeyer, K. L., and Stott, K. L. (2002). The cable trench problem: combining the shortest path and minimum spanning tree problems. Computers & Operations Research, 29(5):441 – 458.
