A Constant-Factor Approximation for the Generalized Cable-Trench Problem

  • Marcelo Benedito UNICAMP
  • Lehilton Pedrosa UNICAMP
  • Hugo Rosado UNICAMP


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.

Palavras-chave: Combinatorial Opttimization, Approximation Algorithm, Generalized Cable-Trench Problem, Cable-Trench Problem


Chlebık, M. and Chlebıkov´a, J. (2008). The steiner tree problem on graphs: Inap- proximability results. Theoretical Computer Science, 406(3):207 – 214.

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.
BENEDITO, Marcelo; PEDROSA, Lehilton ; ROSADO, Hugo . A Constant-Factor Approximation for the Generalized Cable-Trench Problem. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 4. , 2019, Belém. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2019.6399.