Noticias en español
Lower Bounds for Online Matching on the Line
Abstract: In the online matching on the line problem, the task is to match a set of requests R online to a given set of servers S. The distance metric between any two points in R ∪ S is a line metric and the objective for the online algorithm is to minimize the sum of distances between matched server-request pairs. This problem is well-studied and – despite recent improvements – there is still a large gap between the best known lower and upper bounds: The best known deterministic algorithm for the problem is O(log^2(n))-competitive, while the best known deterministic lower bound is 9 .001....
Read MoreAdaptive Computation of Frechet Distance: Upper and Conditional Lower Bound
Abstract: The Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves, and permits to abstract, among other things, differences of resolution between the two curves (with application to morphing, handwriting recognition and protein structure alignment, among others). In 1991, Art and Godau introdued this measure to Computational Geometry, describing an algorithm computing the Fréchet distance between two polygonal curves composed of $n$ and $m$ segments respectively in time within $O(mn\log(mn))$, the first...
Read More