Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 62 Issue 1, February 2015

Section: Approximation Algorithms

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
Mohit Singh, Lap Chi Lau
Article No.: 1
DOI: 10.1145/2629366

In the Minimum Bounded Degree Spanning Tree problem, we are given an undirected graph G = (V, E) with a degree upper bound Bv on each vertex vV, and the task is to find a spanning tree...

Section: Approximation Algorithms

Approximate Verification of the Symbolic Dynamics of Markov Chains
Manindra Agrawal, S. Akshay, Blaise Genest, P. S. Thiagarajan
Article No.: 2
DOI: 10.1145/2629417

A finite-state Markov chain M can be regarded as a linear transform operating on the set of probability distributions over its node set. The iterative applications of M to an initial probability distribution μ0 will...

Section: Approximation Algorithms

Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity
James Aspnes, Hagit Attiya, Keren Censor-Hillel, Faith Ellen
Article No.: 3
DOI: 10.1145/2732263

This article presents a novel implementation of a snapshot object for n processes, with O(log2 b log n) step complexity for update operations and O(log b) step complexity for scan operations,...

Section: Approximation Algorithms

Improved Smoothed Analysis of Multiobjective Optimization
Tobias Brunsch, Heiko Röglin
Article No.: 4
DOI: 10.1145/2699445

We present several new results about smoothed analysis of multiobjective optimization problems. Motivated by the discrepancy between worst-case analysis and practical experience, this line of research has gained a lot of attention in the last...

Section: Approximation Algorithms

Constant-Round Nonmalleable Commitments from Any One-Way Function
Huijia Lin, Rafael Pass
Article No.: 5
DOI: 10.1145/2699446

We show unconditionally that the existence of commitment schemes implies the existence of constant-round nonmalleable commitments; earlier protocols required additional assumptions such as collision-resistant hash functions or...

Section: Approximation Algorithms

Invited Articles Foreword
Victor Vianu
Article No.: 6
DOI: 10.1145/2734885

Section: Approximation Algorithms

On the Complexity of Universal Leader Election
Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, Amitabh Trehan
Article No.: 7
DOI: 10.1145/2699440

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of randomized implicit...

Section: Approximation Algorithms

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ1
Subhash A. Khot, Nisheeth K. Vishnoi
Article No.: 8
DOI: 10.1145/2629614

In this article, we disprove a conjecture of Goemans and Linial; namely, that every negative type metric embeds into ℓ1 with constant distortion. We show that for an arbitrarily small constant δ > 0, for all large enough...

Section: Approximation Algorithms

Measuring and Synthesizing Systems in Probabilistic Environments
Krishnendu Chatterjee, Thomas A. Henzinger, Barbara Jobstmann, Rohit Singh
Article No.: 9
DOI: 10.1145/2699430

The traditional synthesis question given a specification asks for the automatic construction of a system that satisfies the specification, whereas often there exists a preference order among the different systems that satisfy the given...