Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 10 Issue 4, August 2014

Testing Properties of Sparse Images
Dana Ron, Gilad Tsur
Article No.: 17
DOI: 10.1145/2635806

We initiate the study of testing properties of images that correspond to sparse 0/1-valued matrices of size n× n. Our study is related to but different from the study initiated by Raskhodnikova (Proceedings of RANDOM,...

Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
Article No.: 18
DOI: 10.1145/2629672

We show that for every positive ϵ > 0, unless NP ⊂ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2log1-ϵ n by a reduction from the maximum...

Co-Nondeterminism in Compositions: A Kernelization Lower Bound for a Ramsey-Type Problem
Stefan Kratsch
Article No.: 19
DOI: 10.1145/2635808

The field of kernelization offers a rigorous way of studying the ubiquitous technique of data reduction and preprocessing for combinatorially hard problems. A widely accepted definition of useful data reduction is that of a polynomial...

Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal
Stefan Kratsch, Magnus Wahlström
Article No.: 20
DOI: 10.1145/2635810

The Odd Cycle Transversal problem (OCT) asks whether a given undirected graph can be made bipartite by deleting at most k of its vertices. In a breakthrough result, Reed, Smith, and Vetta (Operations Research Letters, 2004) gave a...

Exponential Time Complexity of the Permanent and the Tutte Polynomial
Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, Martin Wahlén
Article No.: 21
DOI: 10.1145/2635812

We show conditional lower bounds for well-studied #P-hard problems:

The number of satisfying assignments of a 2-CNF formula with n variables cannot be computed in time exp(o(n)), and the same is true for computing...

Real-Time Streaming String-Matching
Dany Breslauer, Zvi Galil
Article No.: 22
DOI: 10.1145/2635814

This article presents a real-time randomized streaming string-matching algorithm that uses O(log m) space. The algorithm only makes one-sided small probability false-positive errors, possibly reporting phantom occurrences of the...

Alphabet-Independent Compressed Text Indexing
Djamal Belazzougui, Gonzalo Navarro
Article No.: 23
DOI: 10.1145/2635816

Self-indexes are able to represent a text asymptotically within the information-theoretic lower bound under the kth order entropy model and offer access to any text substring and indexed pattern searches. Their time complexities are not...

Principles of Robust Medium Access and an Application to Leader Election
Baruch Awerbuch, Andrea Richa, Christian Scheideler, Stefan Schmid, Jin Zhang
Article No.: 24
DOI: 10.1145/2635818

This article studies the design of medium access control (MAC) protocols for wireless networks that are provably robust against arbitrary and unpredictable disruptions (e.g., due to unintentional external interference from co-existing networks or...