Abstract Cross-Stitching Using Little Thread ∗ (2009)
We consider the problem of cross-stitching a predetermined pattern on a piece of fabric. We show that computing a stitching sequence that minimizes the amount of thread used when cross-stitching a...
Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM) (2008)
Reza Dorrigiv, Ro López-ortiz, Ro Salinger
Modern microprocessor architectures have gradually incorporated support for parallelism. In the past the degree of parallelism was rather small and as such it could be best modeled as a constant...
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...
Adaptive Analysis of On-line Algorithms (2008)
Reza Dorrigiv Alej, Ro López-ortiz
On-line algorithms are usually analyzed using competitive analysis, in which the performance of on-line algorithm on a sequence is normalized by the performance of the optimal off-line algorithm on...
Abstract On the Separation and Equivalence of Paging Strategies (2008)
Spyros Angelopoulos, Reza Dorrigiv Alej, Ro López-ortiz
It has been experimentally observed that LRU and variants thereof are the preferred strategies for on-line paging. However, under most proposed performance measures for on-line algorithms the...
Optimal Dynamic Video-On-Demand using Adaptive Broadcasting (2008)
Therese Biedl, Erik D. Demaine, Er Golynski, Joseph D. Horton, Ro López-ortiz, Guillaume Poirier, ...
Abstract. We consider the transmission of a movie over a broadcast network to support several viewers who start watching at arbitrary times, after a wait of at most twait minutes. A recent approach...
Online Routing in Convex Subdivisions ∗ Prosenjit Bose (2008)
We consider online routing algorithms for finding 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...
Experimental Evaluation of List Update Algorithms for Data Compression (2007)
Reza Dorrigiv, Ro López-ortiz, J. Ian Munro
Abstract. List update algorithms have been widely used as subroutines in compression schemas, specially after the introduction of the Burrows-Wheeler transform. The Burrows-Wheeler transform (BWT),...
Faster adaptive set intersections for text searching (2006)
Jérémy Barbay, Ro López-ortiz, Tyler Lu
Abstract. The intersection of large ordered sets is a common problem in the context of the evaluation of boolean queries to a search engine. In this paper we engineer a better algorithm for this...
Sharper upper and lower bounds for an approximation scheme for Consensus-Pattern (2005)
Broňa Brejová, Daniel G. Brown, Ian M. Harrower, Ro López-ortiz
Abstract. We present sharper upper and lower bounds for a known polynomial-time approximation scheme due to Li, Ma and Wang [7] for the Consensus-Pattern problem. This NP-hard problem is an...
URL-Enhanced Adaptive Page-Refresh Models (2005)
Robert Warren, Dana Wilkinson, Ro López-ortiz
We study the refresh model required to keep an up to date copy of a web page. This has applications for more efficient and frequent crawling, in the case of search engines, and for higher hit rates...
Finding hidden independent sets in interval graphs. Theoretical Computer Science (2004)
Therese Biedl, Broňa Brejová, Erik D. Demaine, Angèle M. Hamel, Ro López-ortiz
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...
Improved algorithms for the global cardinality constraint (2004)
Claude-guy Quimper, Ro López-ortiz, Peter Van Beek, Alexander Golynski
Abstract. We study the global cardinality constraint (gcc) and propose an O(n 1.5 d) algorithm for domain consistency and an O(cn + dn) algorithm for range consistency, where n is the number of...
A Linear Lower Bound on Index Size for Text Retrieval (2003)
Most information-retrieval systems preprocess the data to produce an auxiliary index structure. Empirically, it has been observed that there is a tradeoff between query response time and the size of...
A fast and simple algorithm for bounds consistency of the alldifferent constraint (2003)
Ro López-ortiz, Claude-guy Quimper, John Tromp, Peter Van Beek
In constraint programming one models a problem by stating constraints on acceptable solutions. The constraint model is then usually solved by interleaving backtracking search and constraint...
An efficient bounds consistency algorithm for the global cardinality constraint (2003)
Claude-guy Quimper, Peter Van Beek, Ro López-ortiz, Er Golynski, Sayyed Bashir Sadjad
Abstract. Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we...
An efficient bounds consistency algorithm for the global cardinality constraint (2003)
Claude-guy Quimper, Er Golynski, Ro López-ortiz, Peter Van Beek
Abstract. Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we...
An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint (2003)
Claude-guy Quimper, Peter Van Beek, Ro López-ortiz, Er Golynski, Sayyed Bashir Sadjad
Abstract. Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we...
Frequency estimation of internet packet streams with limited space (2002)
Erik D. Demaine, Ro López-ortiz, J. Ian Munro
Abstract. We consider a router on the Internet analyzing the statistical properties of a TCP/IP packet stream. A fundamental difficulty with measuring traffic behavior on the Internet is that there...
Robot localization without depth perception (2002)
Erik D. Demaine, Ro López-ortiz, J. Ian Munro
Abstract. Consider the problem of placing reflectors in a 2-D environment in such a way that a robot equipped with a basic laser can always determine its current location. The robot is allowed to...