Alejandro López-Ortiz

TCS Journal 2020 Journal Article

Paid exchanges are worth the price

• Alejandro López-Ortiz
• Marc P. Renault
• Adi Rosén

We consider the list update problem as defined in the seminal work on competitive analysis by Sleator and Tarjan [13]. An instance of the problem consists of a sequence of requests to access items in a linked list. After an item is accessed, that item can be moved to any position forward in the list at no cost (a move called free exchange), and, at any time, any two adjacent items can be swapped at a cost of 1 (a move called paid exchange). The cost to access an item is equal to its current position in the list. The goal is to dynamically rearrange the list so as to minimize the total cost (accrued from accesses and exchanges) over the request sequence. We show a lower bound of 12/11 on the worst-case ratio between the performance of an (offline) optimal algorithm that can only perform free exchanges and that of an (offline) optimal algorithm that can perform both paid and free exchanges. This answers the question of the asymptotic relative power of the two models which has been open since Reingold and Westbrook [11] showed in 1996 that Sleator and Tarjan erred in [13] when they claimed that the two models are equivalent.

I&C Journal 2017 Journal Article

On the list update problem with advice

• Joan Boyar
• Shahin Kamali
• Kim S. Larsen
• Alejandro López-Ortiz

We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial information about the unknown parts of the input in the form of some bits of advice generated by a benevolent offline oracle. We show that advice of linear size is required and sufficient for a deterministic algorithm to achieve an optimal solution or even a competitive ratio better than 15/14. On the other hand, we show that surprisingly two bits of advice are sufficient to break the lower bound of 2 on the competitive ratio of deterministic online algorithms and achieve a deterministic algorithm with a competitive ratio of 1. 6 ¯. In this upper-bound argument, the bits of advice determine the algorithm with smaller cost among three classical online algorithms, Timestamp and two members of the Mtf2 family of algorithms. We also show that Mtf2 algorithms are 2. 5-competitive.

TCS Journal 2017 Journal Article

The within-strip discrete unit disk cover problem

• Robert Fraser
• Alejandro López-Ortiz

We present a study of the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, which is a restricted version of the Discrete Unit Disk Cover (DUDC) problem. For the WSDUDC problem, there exist a set of points and a set of unit disks in the plane, and the points and disk centres are confined to a strip of fixed width. An optimal solution to the WSDUDC problem is a subset of the disks of minimum cardinality that covers all points in the input set. We describe two approximation algorithms for the problem: a 3-approximate algorithm which applies for strips of width at most 0. 8 units, and a general scheme for any strip with less than unit width. We prove that the WSDUDC problem is NP -hard on strips of any fixed width, which is our most interesting result from a theoretical standpoint. The result is also quite surprising, since a number of similar problems are tractable on strips of fixed width. Finally, we discuss how these results may be applied to known DUDC approximation algorithms.

ICRA Conference 2015 Conference Paper

Local policies for efficiently patrolling a triangulated region by a robot swarm

• Daniela Maftuleac
• SeoungKyou Lee
• Sándor P. Fekete
• Aditya Kumar Akash
• Alejandro López-Ortiz
• James McLurkin

We present and analyze methods for patrolling and surveillance in an environment with a distributed swarm of robots with limited capabilities. Our approach is based on a distributed triangulation of the work space, in which a set of p stationary sensors provides coverage control; in addition, there are r mobile robots that can move between the sensors. Building on our prior work on structured exploration of unknown spaces with multi-robot systems, we can make use of a triangulation that is constructed in a distributed fashion and guarantees good local navigation properties, even when sensors and robots have very limited capabilities.

TCS Journal 2014 Journal Article

Multi-target ray searching problems

• Spyros Angelopoulos
• Alejandro López-Ortiz
• Konstantinos Panagiotou

We consider the problem of exploring m concurrent rays using a searcher. The rays are disjoint with the exception of a single common point, and in each ray at most one potential target may be located. The objective is to design search strategies for locating t targets (with t ⩽ m ) while minimizing the search distance traversed. This setting generalizes the extensively studied ray search (or star search) problem, in which the searcher seeks a single target. We apply two different measures for evaluating the efficiency of the search strategy. The first measure is the standard metric in the context of ray-search problems, and compares the total search cost to the cost of an optimal algorithm that has full information on the targets. We present a simple strategy that achieves optimal competitive ratio under this metric. Our main result pertains to the second measure, which is based on a weakening of the optimal cost as proposed by Kirkpatrick [ESA 2009] and McGregor et al. [ESA 2009]. For this model, we present an asymptotically optimal strategy that is within a multiplicative factor of Θ ( log ( m − t ) ) from the optimal search cost. Our results demonstrate that, for both problems, the problem of locating t targets in m rays is essentially as difficult as the problem of locating a single target in m − ( t − 1 ) rays.

TCS Journal 2011 Journal Article

Untangled monotonic chains and adaptive range search

• Diego Arroyuelo
• Francisco Claude
• Reza Dorrigiv
• Stephane Durocher
• Meng He
• Alejandro López-Ortiz
• J. Ian Munro
• Patrick K. Nicholson

We present the first adaptive data structure for two-dimensional orthogonal range search. Our data structure is adaptive in the sense that it gives improved search performance for data that is better than the worst case (Demaine et al. , 2000) [8]; in this case, data with more inherent sortedness. Given n points on the plane, the linear space data structure can answer range queries in O ( log n + k + m ) time, where m is the number of points in the output and k is the minimum number of monotonic chains into which the point set can be decomposed, which is O ( n ) in the worst case. Our result matches the worst-case performance of other optimal-time linear space data structures, or surpasses them when k = o ( n ). Our data structure can be made implicit, requiring no extra space beyond that of the data points themselves (Munro and Suwanda, 1980) [16], in which case the query time becomes O ( k log n + m ). We also present a novel algorithm of independent interest to decompose a point set into a minimum number of untangled, similarly directed monotonic chains in O ( k 2 n + n log n ) time.

IJCAI Conference 2009 Conference Paper

• Spyros Angelopoulos
• Alejandro López-Ortiz

In this paper we address the problem of designing an interruptible system in a setting in which n problem instances, all equally important, must be solved. The system involves scheduling executions of contract algorithms (which offer a tradeoff between allowable computation time and quality of the solution) in m identical parallel processors. When an interruption occurs, the system must report a solution to each of the n problem instances. The quality of this output is then compared to the best-possible algorithm that has foreknowledge of the interruption time and must, likewise, produce solutions to all n problem instances. This extends the well-studied setting in which only one problem instance is queried at interruption time. We propose a schedule which we prove is optimal for the case of a single processor. For multiple processors, we show that the quality of the schedule is within a small factor from optimal.

TCS Journal 2009 Journal Article

On the relative dominance of paging algorithms

• Reza Dorrigiv
• Alejandro López-Ortiz
• J. Ian Munro

In this paper, we give a finer separation of several known paging algorithms using a new technique called relative interval analysis. This technique compares the fault rate of two paging algorithms across the entire range of inputs of a given size, rather than in the worst case alone. Using this technique, we characterize the relative performance of LRU and LRU-2, as well as LRU and FWF, among others. We also show that look-ahead is beneficial for a paging algorithm, a fact that is well known in practice but it was, until recently, not verified by theory.

SODA Conference 2007 Conference Paper

On the separation and equivalence of paging strategies

• Spyros Angelopoulos 0001
• Reza Dorrigiv
• Alejandro López-Ortiz

MFCS Conference 2004 Conference Paper

Efficient View Point Selection for Silhouettes of Convex Polyhedra

• Therese C. Biedl
• Masud Hasan
• Alejandro López-Ortiz

Abstract The silhouette of polyhedra is an important primitive in application areas such as machine vision and computer graphics. In this paper, we study how to select view points of convex polyhedra such that the silhouette satisfies certain properties. Specifically, we give algorithms to find all projections of a convex polyhedron such that a given set of edges, faces and/or vertices appear on the silhouette. We present an algorithm to solve this problem in O ( k 2 ) time for k edges. For orthogonal projections, we give an improved algorithm that is fully adaptive in the number l of connected components formed by the edges, and has a time complexity of O ( k log k + kl ). We then generalize this algorithm to edges and/or faces appearing on the silhouette.

TCS Journal 2004 Journal Article

Finding hidden independent sets in interval graphs

• Therese Biedl
• Broňa Brejová
• Erik D. Demaine
• Angèle M. Hamel
• Alejandro López-Ortiz
• Tomáš Vinař

We design efficient competitive algorithms for discovering hidden information using few queries. Specifically, consider a game in a given set of intervals (and their implied interval graph G) in which our goal is to discover an (unknown) independent set X by making the fewest queries of the form “Is point p covered by an interval in X? ” Our interest in this problem stems from two applications: experimental gene discovery with PCR technology and the game of Battleship (in a 1-dimensional setting). We provide adaptive algorithms for both the verification scenario (given an independent set, is it X?) and the discovery scenario (find X without any information). Under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.

TCS Journal 2004 Journal Article

Longest increasing subsequences in sliding windows

• Michael H Albert
• Alexander Golynski
• Angèle M Hamel
• Alejandro López-Ortiz
• S.Srinivasa Rao
• Mohammad Ali Safari

We consider the problem of finding the longest increasing subsequence in a sliding window over a given sequence (LISW). We propose an output-sensitive data structure that solves this problem in time O(n loglog n+ OUTPUT ) for a sequence of n elements. This data structure substantially improves over the naı̈ve generalization of the longest increasing subsequence algorithm and in fact produces an output-sensitive optimal solution.

TCS Journal 2004 Journal Article

On-line parallel heuristics, processor scheduling and robot searching under the competitive framework

• Alejandro López-Ortiz
• Sven Schuierer

In this paper we investigate parallel searches on m concurrent rays for a point target t located at some unknown distance along one of the rays. A group of p agents or robots moving at unit speed searches for t. The search succeeds when an agent reaches the point t. Given a strategy S the competitive ratio is the ratio of the time needed by the agents to find t using S and the time needed if the location of t had been known in advance. We provide a strategy with competitive ratio of 1+2(m/p−1)(m/(m−p)) m/p and prove that this is optimal. This problem has applications in multiple heuristic searches in AI as well as robot motion planning. The case p=1 is known in the literature as the cow path problem.

TCS Journal 2003 Journal Article

On universally easy classes for NP-complete problems

• Erik D. Demaine
• Alejandro López-Ortiz
• J.Ian Munro

We explore the natural question of whether all NP-complete problems have a common restriction under which they are polynomially solvable. More precisely, we study what languages are universally easy in that their intersection with any NP-complete problem is in P (universally polynomial) or at least no longer NP-complete (universally simplifying). In particular, we give a polynomial-time algorithm to determine whether a regular language is universally easy. While our approach is language-theoretic, the results bear directly on finding polynomial-time solutions to very broad and useful classes of problems.

I&C Journal 2003 Journal Article

Searching and on-line recognition of star-shaped polygons

• Alejandro López-Ortiz
• Sven Schuierer

We study the problem of on-line searching for a target inside a polygon. In particular, we propose a strategy for finding a target of unknown location in a star-shaped polygon with a competitive ratio of 11. 52. We also provide a lower bound of 9 for the competitive ratio of searching in a star-shaped polygon which is close to the upper bound. A similar task is the on-line recognition of a star-shaped polygon P. Here, the robot travels on a path that allows it to decide whether P is star-shaped or not. We present a strategy with a competitive ratio of 28. 85 and give a lower bound of 82 for this problem.

FOCS Conference 2003 Conference Paper

The Cost of Cache-Oblivious Searching

• Michael A. Bender
• Gerth Stølting Brodal
• Rolf Fagerberg
• Dongdong Ge
• Simai He
• Haodong Hu
• John Iacono
• Alejandro López-Ortiz

Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e log/sub B/N block transfers between any two levels of the memory hierarchy. This lower bound holds even if all of the block sizes are limited to be powers of 2. A modified version of the van Emde Boas layout is proposed, whose expected block transfers between any two levels of the memory hierarchy arbitrarily close to [lg e + O(lg lg B/ lgB)] logB N + O(1). This factor approaches lg e /spl ap/ 1. 443 as B increases. The expectation is taken over the random placement of the first element of the structure in memory. As searching in the disk access model (DAM) can be performed in log/sub B/N + 1 block transfers, this result shows a separation between the 2-level DAM and cache-oblivious memory-hierarchy models. By extending the DAM model to k levels, multilevel memory hierarchies can be modeled. It is shown that as k grows, the search costs of the optimal k-level DAM search structure and of the optimal cache-oblivious search structure rapidly converge. This demonstrates that for a multilevel memory hierarchy, a simple cache-oblivious structure almost replicates the performance of an optimal parameterized k-level DAM structure.

SODA Conference 2001 Conference Paper

A linear lower bound on index size for text retrieval

• Erik D. Demaine
• Alejandro López-Ortiz

SODA Conference 2001 Conference Paper

On universally easy classes for NP-complete problems

• Erik D. Demaine
• Alejandro López-Ortiz
• J. Ian Munro

TCS Journal 2001 Journal Article

The ultimate strategy to search on m rays?

• Alejandro López-Ortiz
• Sven Schuierer

We consider the problem of searching on m current rays for a target of unknown location. If no upper bound on the distance to the target is known in advance, then the optimal competitive ratio is 1+2mm/(m−1)m−1. We show that even if an upper bound of D on the distance to the target is known in advance, then the competitive ratio of any search strategy is at least 1+2mm/(m−1)m−1−O(1/log 2 D). This is again optimal – but in a stricter sense. In particular, this result implies the same lower bound for a robot searching for a target on infinite rays and finding it at a distance of D. To show that our lower bound is, indeed, optimal we construct a search strategy that achieves this ratio. Our strategy does not need to know an upper bound on the distance to the target in advance; it achieves a competitive ratio of 1+2mm/(m−1)m−1−O(1/log 2 D) if the target is found at distance D. Finally, we also present a linear time algorithm to compute the strategy that allows the robot to search the farthest for a given competitive ratio C.

SODA Conference 2000 Conference Paper

Adaptive set intersections, unions, and differences

• Erik D. Demaine
• Alejandro López-Ortiz
• J. Ian Munro