Stanford University
Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, 1988 – STOC
In a clustering problem, the aim is to partition a given set of n points in d-dimensional space into k groups, called clusters, so that points within each cluster are near each other. Two objective functions frequently used to measure the performance ...
Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani
Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model-c~led incremental clustering which is based on a careful ...
Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, An Zhu
Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006 – PODS
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying records is to remove identifying fields such as ...
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993 – STOC
A constraint-satisfaction problem is given by a pair I (the instance) and T (the template) of finite relational structures over the same vocabulary. The problem is satisfied if there is a homomorphism from 1 to T. It is well-known that the ...
Rajeev Alur, Tomás Feder, Thomas A. Henzinger
Journal of the ACM, vol. 43,no. 1,1996 – JACM
The most natural, compositional, way of modeling real-time systems uses a dense domain for time. The satistiability of timing constraints that are capable of expressing punctuality in this model, however, is known to be undecidable. We introduce a ...
Journal of Computer and System Sciences, vol. 51,no. 2,1995 – JCSS
Proceedings of the twenty-third annual ACM Symposium on Theory of Computing, STOC 1991, 1991 – STOC
We first consider the problem of partitioning the edges of a graph ~ into bipartite cliques such that the total order of the cliques is minimized, where the order of a clique is the number of vertices in it. It is shown that the problem is ...
Tomás Feder, Rajeev Motwani, Rina Panigrahy, Christopher Olston, Jennifer Widom
We consider a new model for computing with uncertainty. It is desired to compute a function f(X1,...,Xn) where X1,.. •, X,~ are unknown, but guaranteed to lie in specified intervals I1,.. •, I~. It is possible to query the precise value of any ...