"\"Given a metric graph $G=(V,E)$ of $n$ vertices, i.e., a. complete graph with a non-negative real edge cost function. satisfying the triangle inequality, the. \\\\emph{metricity degree} of $G$ is defined as $\\\\beta=\\\\max_{x,y,z \\\\in. V} \\\\big\\\\{ \\\\frac{c(x,y)}{c(x,z)+c(y,z)}\\\\big\\\\} \\\\in. \\\\big[\\\\frac{1}{2},1\\\\big]$. This value is instrumental to establish. the approximability of several $\\\\np$-hard optimization problems. definable on $G$, like for instance the prominent \\\\emph{traveling. salesman problem}, which asks for finding a Hamiltonian cycle of $G$. of minimum total cost. In fact, this problem can be approximated. quite accurately depending on the metricity degree of $G$, namely by. a ratio of either $\\\\frac{2-\\\\beta}{3(1-\\\\beta)}$ or $\\\\frac{3\\\\beta^2}{3. \\\\beta^2-2\\\\beta+1}$, for $\\\\beta < \\\\frac{2}{3}$ or $\\\\beta \\\\geq. \\\\frac{2}{3}$, respectively. Nevertheless, these approximation. algorithms have $O(n^3)$ and $O(n^{2.5} \\\\log ^{1.5} n)$ running. time, respectively, and therefore they are superlinear in the. $\\\\Theta(n^2)$ input size. Thus, since many real-world problems are. modeled by graphs of huge size, their use might turn out to be. unfeasible in practice, and alternative approaches requiring. only $O(n^2)$ time are sought.. However, with this restriction, all the currently available. approaches can only guarantee a 2-approximation ratio for the case $\\\\beta=1$,. which means a. $\\\\frac{2\\\\beta^2}{2\\\\beta^2-2\\\\beta+1}$-approximation ratio for general $\\\\beta < 1$.. %With this restriction, the currently. %most efficient available solution is given by the classic. %\\\\emph{double-MST} heuristic,. %%$\\\\mathtt{Double}\\\\mbox{-}\\\\mathtt{MST~shortcut}$ algorithm,. %which returns a solution within a factor. %$\\\\frac{2\\\\beta^2}{2\\\\beta^2-2\\\\beta+1}$ from the optimum in $O(n^2)$. %time.. In this paper, we show how to elaborate --without affecting the space and time complexity-- one of these. approaches, namely the classic \\\\emph{double-MST} heuristic, in order to obtain a $2\\\\beta$-approximate solution.. This improvement is effective, since we show that the double-MST heuristic has in general a performance ratio. strictly larger than $2 \\\\beta$, and we further show that \\\\emph{any} alternative elaboration of it cannot lead to. a performance ratio better than $2\\\\beta-\\\\epsilon$, for any $\\\\epsilon>0$. Our theoretical results are. complemented with an extensive series of experiments, that show the practical appeal of our approach.\""

Approximating the Metric TSP in Linear Time

D. Bilò;FORLIZZI, LUCA;PROIETTI, GUIDO
2011-01-01

Abstract

"\"Given a metric graph $G=(V,E)$ of $n$ vertices, i.e., a. complete graph with a non-negative real edge cost function. satisfying the triangle inequality, the. \\\\emph{metricity degree} of $G$ is defined as $\\\\beta=\\\\max_{x,y,z \\\\in. V} \\\\big\\\\{ \\\\frac{c(x,y)}{c(x,z)+c(y,z)}\\\\big\\\\} \\\\in. \\\\big[\\\\frac{1}{2},1\\\\big]$. This value is instrumental to establish. the approximability of several $\\\\np$-hard optimization problems. definable on $G$, like for instance the prominent \\\\emph{traveling. salesman problem}, which asks for finding a Hamiltonian cycle of $G$. of minimum total cost. In fact, this problem can be approximated. quite accurately depending on the metricity degree of $G$, namely by. a ratio of either $\\\\frac{2-\\\\beta}{3(1-\\\\beta)}$ or $\\\\frac{3\\\\beta^2}{3. \\\\beta^2-2\\\\beta+1}$, for $\\\\beta < \\\\frac{2}{3}$ or $\\\\beta \\\\geq. \\\\frac{2}{3}$, respectively. Nevertheless, these approximation. algorithms have $O(n^3)$ and $O(n^{2.5} \\\\log ^{1.5} n)$ running. time, respectively, and therefore they are superlinear in the. $\\\\Theta(n^2)$ input size. Thus, since many real-world problems are. modeled by graphs of huge size, their use might turn out to be. unfeasible in practice, and alternative approaches requiring. only $O(n^2)$ time are sought.. However, with this restriction, all the currently available. approaches can only guarantee a 2-approximation ratio for the case $\\\\beta=1$,. which means a. $\\\\frac{2\\\\beta^2}{2\\\\beta^2-2\\\\beta+1}$-approximation ratio for general $\\\\beta < 1$.. %With this restriction, the currently. %most efficient available solution is given by the classic. %\\\\emph{double-MST} heuristic,. %%$\\\\mathtt{Double}\\\\mbox{-}\\\\mathtt{MST~shortcut}$ algorithm,. %which returns a solution within a factor. %$\\\\frac{2\\\\beta^2}{2\\\\beta^2-2\\\\beta+1}$ from the optimum in $O(n^2)$. %time.. In this paper, we show how to elaborate --without affecting the space and time complexity-- one of these. approaches, namely the classic \\\\emph{double-MST} heuristic, in order to obtain a $2\\\\beta$-approximate solution.. This improvement is effective, since we show that the double-MST heuristic has in general a performance ratio. strictly larger than $2 \\\\beta$, and we further show that \\\\emph{any} alternative elaboration of it cannot lead to. a performance ratio better than $2\\\\beta-\\\\epsilon$, for any $\\\\epsilon>0$. Our theoretical results are. complemented with an extensive series of experiments, that show the practical appeal of our approach.\""
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/89400
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact