Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 6 Issue 1, December 2009

Resilient dictionaries
Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano
Article No.: 1
DOI: 10.1145/1644015.1644016

We address the problem of designing data structures in the presence of faults that may arbitrarily corrupt memory locations. More precisely, we assume that an adaptive adversary can arbitrarily overwrite the content of up to δ memory...

An optimal decomposition algorithm for tree edit distance
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
Article No.: 2
DOI: 10.1145/1644015.1644017

The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as...

Improved approximate string matching and regular expression matching on Ziv-Lempel compressed texts
Philip Bille, Rolf Fagerberg, Inge Li Gørtz
Article No.: 3
DOI: 10.1145/1644015.1644018

We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes. We present a time-space trade-off that leads to...

Updating relaxed K-d trees
Amalia Duch, Conrado Martínez
Article No.: 4
DOI: 10.1145/1644015.1644019

In this work we present an in-depth study of randomized relaxed K-d trees. It covers two fundamental aspects: the randomized algorithms that allow to preserve the random properties of relaxed K-d trees and the mathematical analysis...

Approximating connectivity augmentation problems
Zeev Nutov
Article No.: 5
DOI: 10.1145/1644015.1644020

Let G = (V,E) be an undirected graph and let SV. The S-connectivity λSG(u,v) of a node pair (u,v) in G is the...

Trading off space for passes in graph streaming problems
Camil Demetrescu, Irene Finocchi, Andrea Ribichini
Article No.: 6
DOI: 10.1145/1644015.1644021

Data stream processing has recently received increasing attention as a computational paradigm for dealing with massive data sets. Surprisingly, no algorithm with both sublinear space and passes is known for natural graph problems in classical...

Low distortion spanners
Seth Pettie
Article No.: 7
DOI: 10.1145/1644015.1644022

A spanner of an undirected unweighted graph is a subgraph that approximates the distance metric of the original graph with some specified accuracy. Specifically, we say HG is an f-spanner of G if any two...

Minimum cycle bases: Faster and simpler
Kurt Mehlhorn, Dimitrios Michail
Article No.: 8
DOI: 10.1145/1644015.1644023

We consider the problem of computing exact or approximate minimum cycle bases of an undirected (or directed) graph G with m edges, n vertices and nonnegative edge weights. In this problem, a {0, 1} (−1,0,1}) incidence...

Exponential time algorithms for the minimum dominating set problem on some graph classes
Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Ioan Todinca
Article No.: 9
DOI: 10.1145/1644015.1644024

The minimum dominating set problem remains NP-hard when restricted to any of the following graph classes: c-dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, and circle graphs. Developing and using a general approach,...

Optimizing throughput and energy in online deadline scheduling
Ho-Leung Chan, Joseph Wun-Tat Chan, Tak-Wah Lam, Lap-Kei Lee, Kin-Sum Mak, Prudence W. H. Wong
Article No.: 10
DOI: 10.1145/1644015.1644025

This article extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. Specifically, we consider a processor that can vary its speed between 0 and a maximum speed T to minimize its energy...

Admission control to minimize rejections and online set cover with repetitions
Noga Alon, Yossi Azar, Shai Gutner
Article No.: 11
DOI: 10.1145/1644015.1644026

We study the admission control problem in general networks. Communication requests arrive over time, and the online algorithm accepts or rejects each request while maintaining the capacity limitations of the network. The admission control problem...

Jitter regulation for multiple streams
David Hay, Gabriel Scalosub
Article No.: 12
DOI: 10.1145/1644015.1644027

For widely used interactive communication, it is essential that traffic is kept as smooth as possible; the smoothness of the traffic is typically captured by its delay jitter, that is, the difference between the maximal and minimal...

Latency-constrained aggregation in sensor networks
LUCA Becchetti, Alberto Marchetti-Spaccamela, Andrea Vitaletti, Peter Korteweg, Martin Skutella, Leen Stougie
Article No.: 13
DOI: 10.1145/1644015.1644028

A sensor network consists of sensing devices which may exchange data through wireless communication; sensor networks are highly energy constrained since they are usually battery operated. Data aggregation is a possible way to save energy...

Time-dependent multi-scheduling of multicast
Rami Cohen, Dror Rawitz, Danny Raz
Article No.: 14
DOI: 10.1145/1644015.1644029

Many network applications that need to distribute content and data to a large number of clients use a hybrid scheme in which one (or more) multicast channel is used in parallel to a unicast dissemination. This way the application can distribute...

Improved online algorithms for the sorting buffer problem on line metrics
Iftah Gamzu, Danny Segev
Article No.: 15
DOI: 10.1145/1644015.1644030

An instance of the sorting buffer problem consists of a metric space and a server, equipped with a finite-capacity buffer capable of holding a limited number of requests. An additional ingredient of the input is an online sequence of...

Simultaneous source location
Konstantin Andreev, Charles Garrod, Daniel Golovin, Bruce Maggs, Adam Meyerson
Article No.: 16
DOI: 10.1145/1644015.1644031

We consider the problem of simultaneous source location: selecting locations for sources in a capacitated graph such that a given set of demands can be satisfied simultaneously, with the goal of minimizing the number of locations chosen. For...

The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity
Wolfgang Bein, Mordecai J. Golin, Lawrence L. Larmore, Yan Zhang
Article No.: 17
DOI: 10.1145/1644015.1644032

There exist several general techniques in the literature for speeding up naive implementations of dynamic programming. Two of the best known are the Knuth-Yao quadrangle inequality speedup and the SMAWK algorithm for finding the row-minima of...

Approximating the minimum quadratic assignment problems
Refael Hassin, Asaf Levin, Maxim Sviridenko
Article No.: 18
DOI: 10.1145/1644015.1644033

We consider the well-known minimum quadratic assignment problem. In this problem we are given two n × n nonnegative symmetric matrices A = (aij) and B = (bij). The...

Quantum algorithms for Simon's problem over nonabelian groups
Gorjan Alagic, Cristopher Moore, Alexander Russell
Article No.: 19
DOI: 10.1145/1644015.1644034

Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding “hidden shifts” of Z2n provided the first algebraic problem for which quantum computers are exponentially faster than their...

Computing rank-convolutions with a mask
László Babai, Pedro F. Felzenszwalb
Article No.: 20
DOI: 10.1145/1644015.1644035

Rank-convolutions have important applications in a variety of areas such as signal processing and computer vision. We define a mask as a function taking only values zero and infinity. Rank-convolutions with masks are of special interest to...

Inverse auctions: Injecting unique minima into random sets
F. Thomas Bruss, Guy Louchard, Mark Daniel Ward
Article No.: 21
DOI: 10.1145/1644015.1644036

We consider auctions in which the winning bid is the smallest bid that is unique. Only the upper-price limit is given. Neither the number of participants nor the distribution of the offers are known, so that the problem of placing a bid to win...