enter search term and/or author name
Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
We consider a class of multivariate recurrences frequently arising in the worst-case analysis of Davis-Putnam-style exponential-time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these...
Succinct ordinal trees with level-ancestor queries
Richard F. Geary, Rajeev Raman, Venkatesh Raman
We consider succinct or space-efficient representations of trees that efficiently support a variety of navigation operations. We focus on static ordinal trees, that is, arbitrary static rooted trees where the children of each node are...
Melding priority queues
Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, Uri Zwick
We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) amortized time, where n is an upper bound on the number of elements in the priority queue, can be...
Approximate distance oracles for unweighted graphs in expected O(n2) time
Surender Baswana, Sandeep Sen
Let G = (V, E) be an undirected graph on n vertices, and let δ(u, v) denote the distance in G between two vertices u and v. Thorup and Zwick showed that for any positive...
Experimental analysis of dynamic all pairs shortest path algorithms
Camil Demetrescu, Giuseppe F. Italiano
We present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. We describe our implementations of the recent dynamic algorithms of King  and of Demetrescu and Italiano , and compare...
Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch
Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each applicant and each post...
When indexing equals compression: Experiments with compressing suffix arrays and applications
Luca Foschini, Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter
We report on a new experimental analysis of high-order entropy-compressed suffix arrays, which retains the theoretical performance of previous work and represents an improvement in practice. Our experiments indicate that the resulting text index...
A general approach to online network optimization problems
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (Seffi) Naor
We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design problem, we have a communication network known to the...
Optimally scheduling video-on-demand to minimize delay when sender and receiver bandwidth may differ
William Evans, David Kirkpatrick
We establish tight bounds on the intrinsic cost (either minimizing delay d for fixed sender and receiver bandwidths, or minimizing sender bandwidth for fixed delay and receiver bandwidth) of broadcasting a video of length m over a...
Computing equilibria for a service provider game with (Im)perfect information
Rene Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking
We study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. Suppose a provider offers a service to a set of potential customers. Each...
Generic quantum Fourier transforms
Cristopher Moore, Daniel Rockmore, Alexander Russell
The quantum Fourier transform (QFT) is a principal ingredient appearing in many efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by “quantizing” the highly...