Search ACM DL

Search Issue

enter search term and/or author name

**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 *S* ⊆ *V*. The *S-connectivity* λ^{S}_{G}(*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 *H* ⊆ *G* 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* = (*a _{ij}*) and

**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 Z_{2}^{n} 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...