| Full text | |
| Author(s): |
Benedito, Marcelo P. L.
;
Pedrosa, Lehilton L. C.
;
Rosado, Hugo K. K.
;
Ferreira, CE
;
Lee, O
;
Miyazawa, FK
Total Authors: 6
|
| Document type: | Journal article |
| Source: | PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 10-pg., 2021-01-01. |
| Abstract | |
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) | |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 19/10400-2 - Approximation and parameterized algorithms for pair connectivity problems |
| Grantee: | Marcelo Pinheiro Leite Benedito |
| Support Opportunities: | Scholarships in Brazil - Doctorate |