enter search term and/or author name
We present a new analysis of the well-known family of multiplicative hash functions, and improved deterministic algorithms for selecting “good” hash functions. The main motivation is realization of deterministic dictionaries with fast...
Questions about order versus disorder in systems and models have been fascinating scientists over the years. In computer science, order is intimately related to sorting, commonly meant as the task of arranging keys in increasing or decreasing...
The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra's shortest path algorithm. Although asyptotically efficient, it is not as fast in practice as other heap implementations. Expanding on ideas of...
Alternation and redundancy analysis of the intersection problem
Jérémy Barbay, Claire Kenyon
Article No.: 4
The intersection of sorted arrays problem has applications in search engines such as Google. Previous work has proposed and compared deterministic algorithms for this problem, in an adaptive analysis based on the encoding size of a...
Randomized minimum spanning tree algorithms using exponentially fewer random bits
Seth Pettie, Vijaya Ramachandran
Article No.: 5
For many fundamental problems there exist randomized algorithms that are asymptotically optimal and are superior to the best-known deterministic algorithm. Among these are the minimum spanning tree (MST) problem, the MST sensitivity analysis...
A faster and simpler fully dynamic transitive closure
Article No.: 6
We obtain a new fully dynamic algorithm for maintaining the transitive closure of a directed graph. Our algorithm maintains the transitive closure matrix in a total running time of O(mn + (ins + del) ·...
Consider a digraph with n vertices. For any fixed value k, we present linear- and almost-linear-time algorithms to find a cycle of length ≥ k, if one exists. We also find a cycle that has length ≥ log n/log log...
Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding rectangular layouts is a key problem. We study...
The priority R-tree: A practically efficient and worst-case optimal R-tree
Lars Arge, Mark De Berg, Herman Haverkort, Ke Yi
Article No.: 9
We present the priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using O((N/B)1−1/d+T/B) I/Os, where N is the number of...
Approximate distance oracles for geometric spanners
Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel Smid
Article No.: 10
Given an arbitrary real constant ϵ > 0, and a geometric graph G in d-dimensional Euclidean space with n points, O(n) edges, and constant dilation, our main result is a data structure that answers (1...
Improved bounds for scheduling conflicting jobs with minsum criteria
Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai
Article No.: 11
We consider a general class of scheduling problems where a set of conflicting jobs needs to be scheduled (preemptively or nonpreemptively) on a set of machines so as to minimize the weighted sum of completion times. The conflicts among jobs...
This article considers the problem of robustly emulating a shared atomic memory over a distributed message-passing system where processes can fail by crashing and possibly recover. We revisit the notion of atomicity in the crash-recovery context...
Faster approximation schemes for fractional multicommodity flow problems
Article No.: 13
We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of the minimum possible dependencies on the number of commodities k. We show that by modifying the algorithms by Garg and...
Hierarchical bin buffering: Online local moments for dynamic external memory arrays
Daniel Lemire, Owen Kaser
Article No.: 14
For a massive I/O array of size n, we want to compute the first N local moments, for some constant N. Our simpler algorithms partition the array into consecutive ranges called bins, and apply not only to local-moment queries,...
Path decomposition under a new cost measure with applications to optical network design
Elliot Anshelevich, Lisa Zhang
Article No.: 15
We introduce a problem directly inspired by its application to DWDM (dense wavelength division multiplexing) network design. We are given a set of demands to be carried over a network. Our goal is to choose a route for each demand and to...