Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG) - Special Issue on SODA'11, Volume 9 Issue 3, June 2013

Foreword to the Special Issue on SODA’11
Shuchi Chawla, Prasad Raghavendra, Dana Randall
Article No.: 20
DOI: 10.1145/2483699.2483700

An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
Nir Ailon, Edo Liberty
Article No.: 21
DOI: 10.1145/2483699.2483701

The problems of random projections and sparse reconstruction have much in common and individually received much attention. Surprisingly, until now they progressed in parallel and remained mostly separate. Here, we employ new tools from probability...

Persistent Predecessor Search and Orthogonal Point Location on the Word RAM
Timothy M. Chan
Article No.: 22
DOI: 10.1145/2483699.2483702

We answer a basic data structuring question (e.g., raised by Dietz and Raman [1991]): Can van Emde Boas trees be made persistent, without changing their asymptotic query/update time? We present a (partially) persistent data structure that supports...

On the Complexity of Approximating a Nash Equilibrium
Constantinos Daskalakis
Article No.: 23
DOI: 10.1145/2483699.2483703

We show that computing a relatively (i.e., multiplicatively as opposed to additively) approximate Nash equilibrium in two-player games is PPAD-complete, even for constant values of the approximation. Our result is the first constant...

Bin Packing via Discrepancy of Permutations
Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß
Article No.: 24
DOI: 10.1145/2483699.2483704

A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a...

Optimal Pattern Matching in LZW Compressed Strings
Paweł Gawrychowski
Article No.: 25
DOI: 10.1145/2483699.2483705

We consider the following variant of the classical pattern matching problem: given an uncompressed pattern p[1..m] and a compressed representation of a string t[1..N], does p occur in t? When t is...

Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
T. S. Jayram, David P. Woodruff
Article No.: 26
DOI: 10.1145/2483699.2483706

The Johnson-Lindenstrauss transform is a dimensionality reduction technique with a wide range of applications to theoretical computer science. It is specified by a distribution over projection matrices from Rn → Rk where...

Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
Jakub Łącki
Article No.: 27
DOI: 10.1145/2483699.2483707

This article presents a new deterministic algorithm for decremental maintenance of the transitive closure in a directed graph. The algorithm processes any sequence of edge deletions in O(mn) time and answers queries in constant time....

Sparse Euclidean Spanners with Tiny Diameter
Shay Solomon
Article No.: 28
DOI: 10.1145/2483699.2483708

In STOC’95, Arya et al. [1995] showed that for any set of n points in Rd, a (1 + ε)-spanner with diameter at most 2 (respectively, 3) and O(n log n) edges (respectively, O(n...