1,721,001 research outputs found
Characterization Results for the Poset Based Representation of Topological Relations - II: Intersection and Union
No full text@article{DBLP:journals/informaticaSI/ForlizziN00,
author = {Luca Forlizzi and
Enrico Nardelli},
title = {Characterization Results for the Poset Based Representation
of Topological Relations - II: Intersection and Union.},
journal = {Informatica (Slovenia)},
volume = {24},
number = {1},
year = {2000},
bibsource = {DBLP, http://dblp.uni-trier.de}
Characterization Results for the Poset Based Representation of Topological Relations - I: Introduction and Models
No full text@article{DBLP:journals/informaticaSI/ForlizziN99,
author = {Luca Forlizzi and
Enrico Nardelli},
title = {Characterization Results for the Poset Based Representation
of Topological Relations - I: Introduction and Models.},
journal = {Informatica (Slovenia)},
volume = {23},
number = {2},
year = {1999},
bibsource = {DBLP, http://dblp.uni-trier.de}
Some Results on the Modelling of Spatial Data
No full text@proceedings{DBLP:conf/sofsem/1998,
editor = {Branislav Rovan},
title = {SOFSEM '98: Theory and Practice of Informatics, 25th Conference
on Current Trends in Theory and Practice of Informatics, Jasn{'a},
Slovakia, November 21-27, 1998, Proceedings},
booktitle = {SOFSEM},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {1521},
year = {1998},
isbn = {3-540-65260-4},
bibsource = {DBLP, http://dblp.uni-trier.de}
Approximating the Metric TSP in Linear Time
No full textGiven a metric graph G = (V,E) of n vertices, i.e., a complete graph with an edge cost function c:V ×V →R ≥ 0 satisfying the triangle inequality, the metricity degree of G is defined as β=maxx,y,z∈V{c(x,y)c(x,z)+c(y,z)}∈[12,1] . This value is instrumental to establish the approximability of several NP-hard optimization problems definable on G, like for instance the prominent 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 2−β3(1−β) or 3β23β2−2β+1 , for β<23 or β≥23 , respectively. Nevertheless, these approximation algorithms have O(n 3) and O(n 2.5 log1.5 n) running time, respectively, and therefore they are superlinear in the Θ(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 the 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 β= 1, which means a 2β22β2−2β+1 -approximation ratio for general β< 1. In this paper, we show how to enhance –without affecting the space and time complexity– one of these approaches, namely the classic double-MST heuristic, in order to obtain a 2β-approximate solution. This improvement is effective, since we show that the double-MST heuristic has in general a performance ratio strictly larger that 2 β, and we further show that any re-elaboration of the shortcutting phase therein provided, cannot lead to a performance ratio better than 2β
Approximating the Metric TSP in Linear Time
No full textGiven a metric graph of vertices, i.e., a
complete graph with an edge cost function satisfying the triangle inequality, the
\emph{metricity degree} of is defined as . This value is instrumental to establish
the approximability of several \np-hard optimization problems
definable on , like for instance the prominent \emph{traveling
salesman problem}, which asks for finding a Hamiltonian cycle of
of minimum total cost. In fact, this problem can be approximated
quite accurately depending on the metricity degree of , namely by
a ratio of either or , for or , respectively. Nevertheless, these approximation
algorithms have and running
time, respectively, and therefore they are superlinear in the
input size. Thus, since many real-world problems are
modeled by graphs of huge size, their use might turn out to be
unfeasible in the practice, and alternative approaches requiring
only linear time are sought. With this restriction, the currently
most efficient available solution is given by the classic
\mathtt{Double}\mbox{-}\mathtt{MST \ shortcut} algorithm, which in
time returns a solution within a factor
from the optimum. In this
paper, we develop an enhanced but still linear-time version of this
latter algorithm, which returns a -approximate solution, and
thus always outperforms its counterpart. Indeed, we show that for
any , the performance ratio of the double-tree
shortcutting algorithm is strictly larger than .
Furthermore, as a by-product of our result, it turns out that one of
the most efficient heuristic for the metric TSP, namely the
$\mathtt{Double}\mbox{-}\mathtt{MST\ Min}\mbox{-}\mathtt{weight\
shortcut}2\beta$. Previously, only the
straightforward performance guarantee of 2 was known for this
heuristic. Computational experiments suggest that our algorithm
computes solutions of comparable quality to those produced by the
Christofides algorithm, while requiring a significantly smaller
running time
Approximating the Metric TSP in Linear Time
No full textGiven 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 metricity degree of G is defined as β=maxx,y,z∈V{c(x,y)c(x,z)+c(y,z)}∈[12,1] . This value is instrumental to establish the approximability of several NP-hard optimization problems definable on G, like for instance the prominent 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 2−β3(1−β) or 3β23β2−2β+1 , for β0. Our theoretical results are complemented with an extensive series of experiments, that show the practical appeal of our approach
Region-Based Querz Languages for Spatial Databases in the Topological Data Model
No full text@proceedings{DBLP:conf/ssd/2003,
editor = {Thanasis Hadzilacos and
Yannis Manolopoulos and
John F. Roddick and
Yannis Theodoridis},
title = {Advances in Spatial and Temporal Databases, 8th International
Symposium, SSTD 2003, Santorini Island, Greece, July 24-27, 2003,
Proceedings},
booktitle = {SSTD},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {2750},
year = {2003},
isbn = {3-540-40535-6},
bibsource = {DBLP, http://dblp.uni-trier.de}
- …
