Exceeding expectations and clustering uncertain data

Database technology is playing an increasingly important role in understanding and solving large-scale and complex scientific and societal problems and phenomena, for instance, understanding biological networks, climate modeling, elec-tronic markets, etc. In these settings, uncertainty or impre-cise information is a pervasive issue that becomes a serious impediment to understanding and effectively utilizing such systems. Clustering is one of the key problems in this con-text. In this paper we focus on the problem of clustering, specif-ically the k-center problem. Since the problem is NP-Hard in deterministic setting, a natural avenue is to consider ap-proximation algorithms with a bounded performance ratio. In an earlier paper Cormode and McGregor had considered certain variants of this problem, but failed to provide ap-proximations that preserved the number of centers. In this paper we remedy the situation and provide true approxima-tion algorithms for a wider class of these problems. However, the key aspect of this paper is to devise gen-eral techniques for optimization under uncertainty. We show that a particular formulation which uses the contribution of a random variable above its expectation is useful in this context. We believe these techniques will find wider appli-cations in optimization under uncertainty