Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 57 Issue 2, January 2010

Linear-time approximation schemes for clustering problems in any dimensions
Amit Kumar, Yogish Sabharwal, Sandeep Sen
Article No.: 5
DOI: 10.1145/1667053.1667054

We present a general approach for designing approximation algorithms for a fundamental class of geometric clustering problems in arbitrary dimensions. More specifically, our approach leads to simple randomized algorithms for the k-means,...

Schema mapping discovery from data instances
Georg Gottlob, Pierre Senellart
Article No.: 6
DOI: 10.1145/1667053.1667055

We introduce a theoretical framework for discovering relationships between two database instances over distinct and unknown schemata. This framework is grounded in the context of data exchange. We formalize the problem of understanding the...

The nested chinese restaurant process and bayesian nonparametric inference of topic hierarchies
David M. Blei, Thomas L. Griffiths, Michael I. Jordan
Article No.: 7
DOI: 10.1145/1667053.1667056

We present the nested Chinese restaurant process (nCRP), a stochastic process that assigns probability distributions to ensembles of infinitely deep, infinitely branching trees. We show how this stochastic process can be used as a prior...

Tight bounds for clock synchronization
Christoph Lenzen, Thomas Locher, Roger Wattenhofer
Article No.: 8
DOI: 10.1145/1667053.1667057

We present a novel clock synchronization algorithm and prove tight upper and lower bounds on the worst-case clock skew that may occur between any two participants in any given distributed system. More importantly, the worst-case clock skew between...

The complexity of temporal constraint satisfaction problems
Manuel Bodirsky, Jan Kára
Article No.: 9
DOI: 10.1145/1667053.1667058

A temporal constraint language is a set of relations that has a first-order definition in(Q;<), the dense linear order of the rational numbers. We present a complete complexity classification of the constraint satisfaction problem (CSP)...

The next 700 data description languages
Kathleen Fisher, Yitzhak Mandelbaum, David Walker
Article No.: 10
DOI: 10.1145/1667053.1667059

In the spirit of Landin, we present a calculus of dependent types to serve as the semantic foundation for a family of languages called data description languages. Such languages, which include pads, datascript, and packettypes, are designed...

A constructive proof of the general lovász local lemma
Robin A. Moser, Gábor Tardos
Article No.: 11
DOI: 10.1145/1667053.1667060

The Lovász Local Lemma discovered by Erdős and Lovász in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, József Beck was...