09171 Executive Summary -- Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)
Barbay, Jérémy, Klein, Rolf, López-Ortiz, Alejandro, Niedermeier, Rolf
Traditionally the analysis of algorithms measures the complexity of a problem or algorithm in terms of the worst-case behavior over all inputs of a given size. However, in certain cases an improved...
09171 Abstracts Collection -- Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)
Barbay, Jérémy, Klein, Rolf, López-Ortiz, Alejandro, Niedermeier, Rolf
From 19.01. to 24.04.2009, the Dagstuhl Seminar 09171 ``Adaptive, Output Sensitive, Online and Parameterized Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the...
Fast String Sorting Using Order-Preserving Compression (2008)
Alejandro López-ortiz, Mohammad Ali Safari
We give experimental evidence for the benefits of order-preserving compression in sorting algorithms. While, in general, any algorithm might benefit from compressed data because of reduced paging...
Algorithmic Foundations of the Internet (2008)
In this paper we survey the field of Algorithmic Foundations of the Internet, which is a new area within theoretical computer science. We consider six sample topics that illustrate the techniques and...
MOHAMMAD ALI SAFARI Universiy of British Columbia (2008)
Alejandro López-ortiz, Hossein Sheikhattar, Ro López-ortiz, Mehdi Mirzazadeh, Hossein Sheikhattar, David R. Cheriton
We give experimental evidence for the benefits of order preserving compression in sorting algorithms. While in general any algorithm might benefit from compressed data due to reduced paging...
List Update with Locality of Reference: MTF Outperforms All Other Algorithms (2008)
Spyros Angelopoulos, Reza Dorrigiv, Alejandro López-ortiz
It has been observed that in practice, typical request sequences for the list update problem exhibit a certain degree of locality of reference. We first extend the locality of reference model for the...
Search Algorithms for Unstructured Peer-to-Peer Networks (2008)
Reza Dorrigiv, Alejandro López-ortiz
Abstract—We study the performance of several search algorithms on unstructured peer-to-peer networks, both using classic search algorithms such as flooding and random walk, as well as a new hybrid...
Alejandro López-ortiz, Daniel M. Germán
We propose a caching protocol designed to automatically mirror heavily accessed WWW pages in a distributed and temporal fashion. The proposed caching mechanism differs from proxy type mechanisms in...
1 This report contains the work which was presented to fulfill the requirements of the
Timothy M. Chan, Alexander Golynski, Alejandro López-ortiz, Claude-guy Quimper
We consider two variants of the well-known “sailor in the fog ” puzzle. The first version (the “asteroid surveying” problem) is set in three dimensions and asks for the shortest curve that...
Linear Pattern Matching of Repeated Substrings (2007)
This paper attempts to explain Weiner's result in a more accessible manner. 2 Basic Definitions and Notation
New Lower Bounds for Element Distinctness on a One-tape Turing Machine (2007)
It is shown that the Element Distinctness Problem (n numbers of k log n bits each, k 2) on a one-tape Turing machine takes time proportional to almost the square of the size of the input. The proof...
Reasoning and Knowledge over Impossible Worlds (2007)
We study the desired/required abilities of an intelligent agent capable of reasoning about worlds that it knows to be nonexistent. Special attention is given to the Probabilistic Reasoning Model...
The complexity of implicit and space-efficient priority queues (2005)
Mortensen, Christian W, Pettie, Seth, Dehne, Frank, López-Ortiz, Alejandro, Sack, Jörg-Rüdiger
Identifying frequent items in sliding windows over on-line packet streams (2003)
Lukasz Golab, Alejandro López-ortiz, David Dehaan, J. Ian Munro
Internet traffic patterns are believed to obey the power law, implying that most of the bandwidth is consumed by a small set of heavy users. Hence, queries that return a list of frequently occurring...
Identifying frequent items in sliding windows over on-line packet streams (2003)
Lukasz Golab, Alejandro López-ortiz, David Dehaan, J. Ian Munro
Internet traffic patterns are believed to obey the power law, implying that most of the bandwidth is consumed by a small set of heavy users. Hence, queries that return a list of frequently occurring...
Online Routing in Convex Subdivisions (2000)
Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Alejandro López-Ortiz, ...
. We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
Adaptive Set Intersections, Unions, and Differences (2000)
Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro
Motivated by boolean queries in text database systems, we consider the problems of finding the intersection, union, or difference of a collection of sorted sets. While the worst-case complexity of...
Going Home Through an Unknown Street (1998)
Christian Icking, Alejandro López-Ortiz, Sven Schuierer, Christian Icking Alej, Ines Semrau
We present a new strategy for searching for a goal in a street. The strategy works in two phases. First it follows an angular bisector, then it uses circular arcs based only on one side of the...
Alejandro López-Ortiz, Sven Schuierer
A fundamental problem in robotics is to compute a path for a robot from its current location to a given goal. In this paper we consider the problem of a robot equipped with an on-board vision system...
A Multicollaborative Push-Caching HTTP Protocol for the WWW (1995)
Alejandro López-ortiz, Daniel M. Germán
We propose a caching protocol designed to automatically mirror heavily accessed WWW pages in a distributed and temporal fashion. The proposed caching mechanism differs from proxy type mechanisms in...
Simple, Efficient and Robust Strategies to Traverse Streets (1995)
Alejandro López-Ortiz, Sven Schuierer
We present a family of strategies for the problem of searching in an unknown street for a target of unknown location. We show that a robot using a strategy from this family follows a path that is at...
Going Home Through an Unknown Street (1995)
Alejandro López-Ortiz, Sven Schuierer
We consider the problem of a robot traversing an unknown polygon with the aid of standard visibility. The robot has to find a path from a starting point s to a target point g. We provide upper and...
Probabilistic Complexity Classes (1994)
The purpose of this work is to present an overview of the class of problems solvable in probabilistic polynomial time with double sided error (PP ). We explore the relationship of PP to other...