enter search term and/or author name
A variable can be multiplied by a given set of fixed-point constants using a multiplier block that consists exclusively of additions, subtractions, and shifts. The generation of a multiplier block from the set of constants is known as the multiple...
We show that a wide class of linear cost measures (such as the number of leaves) in random d-dimensional point quadtrees undergo a change in limit laws: If the dimension d = 1, …, 8, then the limit law is normal; if...
We introduce a new data structuring paradigm in which operations can be performed on a data structure not only in the present, but also in the past. In this new paradigm, called retroactive data structures, the historical sequence of...
We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from O(mn2) to O(m2) and the space...
Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch
Article No.: 15
An instance of the stable marriage problem is an undirected bipartite graph G = (X ∪ W, E) with linearly ordered adjacency lists with ties allowed in the ordering. A matching M is a set of edges, no...
Deterministic sampling and range counting in geometric data streams
Amitabha Bagchi, Amitabh Chaudhary, David Eppstein, Michael T. Goodrich
Article No.: 16
We present memory-efficient deterministic algorithms for constructing ε-nets and ε-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation...
A simple entropy-based algorithm for planar point location
Sunil Arya, Theocharis Malamatos, David M. Mount
Article No.: 17
Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficiently....
An algorithm for deciding zero equivalence of nested polynomially recurrent sequences
Article No.: 18
We introduce the class of nested polynomially recurrent sequences which includes a large number of sequences that are of combinatorial interest. We present an algorithm for deciding zero equivalence of these sequences, thereby providing a new...
In this article, we address a new version of dynamic pattern matching. The dynamic text and static pattern matching problem is the problem of finding a static pattern in a text that is continuously being updated. The goal is to report all...
Compressed representations of sequences and full-text indexes
Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, Gonzalo Navarro
Article No.: 20
Given a sequence S = s1s2…sn of integers smaller than r = O(polylog(n)), we show how S can be represented using...
Let T be a string with n characters over an alphabet of constant size. A recent breakthrough on compressed indexing allows us to build an index for T in optimal space (i.e., O(n) bits), while supporting very...
The relative worst order ratio for online algorithms
Joan Boyar, Lene M. Favrholdt
Article No.: 22
We define a new measure for the quality of online algorithms, the relative worst order ratio, using ideas from the max/max ratio [Ben-David and Borodin 1994] and from the random order ratio [Kenyon 1996]. The new ratio is used to compare...
Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy
L. Becchetti, J. Könemann, S. Leonardi, M. Páal
Article No.: 23
In the multicommodity rent-or-buy (MROB) network design problems, we are given a network together with a set of k terminal pairs (s1, t1), …, (sk,...
The NP-completeness column: Finding needles in haystacks
David S. Johnson
Article No.: 24
This is the 26th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book “Computers and Intractability: A Guide to the Theory of...