enter search term and/or author name
Linear-time approximation schemes for clustering problems in any dimensions
Amit Kumar, Yogish Sabharwal, Sandeep Sen
Article No.: 5
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,...
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
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...
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
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)...
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
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...