Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 58 Issue 5, October 2011

Smoothed Analysis of the k-Means Method
David Arthur, Bodo Manthey, Heiko Röglin
Article No.: 19
DOI: 10.1145/2027216.2027217

The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between...

Hardness of Approximating Flow and Job Shop Scheduling Problems
Monaldo Mastrolilli, Ola Svensson
Article No.: 20
DOI: 10.1145/2027216.2027218

We consider several variants of the job shop problem that is a fundamental and classical problem in scheduling. The currently best approximation algorithms have worse than logarithmic performance guarantee, but the only previously known...

Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi, Dániel Marx
Article No.: 21
DOI: 10.1145/2027216.2027219

We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for...

Invited Articles Foreword
Victor Vianu
Article No.: 22
DOI: 10.1145/2027216.2027220

Deterministic Distributed Vertex Coloring in Polylogarithmic Time
Leonid Barenboim, Michael Elkin
Article No.: 23
DOI: 10.1145/2027216.2027221

Consider an n-vertex graph G = (V, E) of maximum degree Δ, and suppose that each vertex vV hosts a processor. The processors are allowed to communicate only with their neighbors in...