On the Inapproximability of the Cable-Trench Problem

Autor(es)

Benedito, Marcelo P. L. ; Pedrosa, Lehilton L. C. ; Rosado, Hugo K. K. ; Ferreira, CE ; Lee, O ; Miyazawa, FK

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 10-pg., 2021-01-01.

Resumo

The Cable-Trench Problem (CTP) is an optimization problem that generalizes both the Single-Destination Shortest Path Problem and the Minimum Spanning Tree Problem. Given an edge weighted graph with a special root vertex and parameters tau, gamma >= 0, the objective is to find a rooted spanning tree that minimizes the weight of the tree, scaled by tau, plus the sum of the weights over all shortest paths from the root, scaled by gamma. While each of the generalized problems are well-known to be polynomial-time solvable, CTP is NP-hard. In this paper, we show that even finding an approximation with factor of 1.000475 is NP-hard, thus ruling out the existence of a polynomial-time approximation scheme, unless P = NP. (C) 2021 The Authors. Published by Elsevier B.V. (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 19/10400-2 - Algoritmos de aproximação e parametrizados para problemas de conectividade de pares
• Beneficiário: Marcelo Pinheiro Leite Benedito
• Modalidade de apoio: Bolsas no Brasil - Doutorado