"\"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.\""

`http://hdl.handle.net/11697/89400`

Titolo: | Approximating the Metric TSP in Linear Time |

Autori interni: | FORLIZZI, LUCA PROIETTI, GUIDO |

Data di pubblicazione: | 2011 |

Rivista: | THEORY OF COMPUTING SYSTEMS |

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.\"" |

Handle: | http://hdl.handle.net/11697/89400 |

Appare nelle tipologie: | 1.1 Articolo in rivista |