Inspired by the concept of stability of approximation, we consider the following (re)optimization problem: Given a minimum-cost Hamiltonian cycle of a complete non-negatively real weighted graph G= (V, E, c) obeying the strengthened triangle inequality (i.e., for some strength factor 1 / 2 ≤ β< 1, we have that ∀ u, v, z∈ V, c(u, z) ≤ β(c(u, v) + c(v, z))), and given a vertex v whose removal from G (resp., addition to G), along with all its incident edges, produces a new weighted graph still obeying the strengthened triangle inequality, find a minimum-cost Hamiltonian cycle of the modified graph. This problem is known to be NP-hard, but we show that it admits a PTAS, which just consists of either returning the old optimal cycle (after having by-passed the removed node), or instead computing (for finitely many inputs) a new optimal solution from scratch − depending on the required accuracy in the approximation. Then, we turn our attention to the case in which a minimum-cost Hamiltonian path is given instead, and the underlying graph obeys the relaxed triangle inequality. Here, if one edge weight is increased, and, denotes the relaxation factor of the original and the modified graph, respectively, then we show how to obtain an approximation of, which improves over existing solutions as soon as.

### Stability of reapproximation algorithms for the β-metric traveling Salesman (path) problem

#### Abstract

Inspired by the concept of stability of approximation, we consider the following (re)optimization problem: Given a minimum-cost Hamiltonian cycle of a complete non-negatively real weighted graph G= (V, E, c) obeying the strengthened triangle inequality (i.e., for some strength factor 1 / 2 ≤ β< 1, we have that ∀ u, v, z∈ V, c(u, z) ≤ β(c(u, v) + c(v, z))), and given a vertex v whose removal from G (resp., addition to G), along with all its incident edges, produces a new weighted graph still obeying the strengthened triangle inequality, find a minimum-cost Hamiltonian cycle of the modified graph. This problem is known to be NP-hard, but we show that it admits a PTAS, which just consists of either returning the old optimal cycle (after having by-passed the removed node), or instead computing (for finitely many inputs) a new optimal solution from scratch − depending on the required accuracy in the approximation. Then, we turn our attention to the case in which a minimum-cost Hamiltonian path is given instead, and the underlying graph obeys the relaxed triangle inequality. Here, if one edge weight is increased, and, denotes the relaxation factor of the original and the modified graph, respectively, then we show how to obtain an approximation of, which improves over existing solutions as soon as.
##### Scheda breve Scheda completa Scheda completa (DC)
2018
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11697/128495`
• ND
• 0
• ND