Exceeding expectations and clustering uncertain data

ABSTRACT

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, electronic markets, etc. In these settings, uncertainty or imprecise 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 context.

In this paper we focus on the problem of clustering, specifically the k-center problem. Since the problem is NP-Hard in deterministic setting, a natural avenue is to consider approximation algorithms with a bounded performance ratio. In an earlier paper Cormode and McGregor had considered certain variants of this problem, but failed to provide approximations that preserved the number of centers. In this paper we remedy the situation and provide true approximation algorithms for a wider class of these problems.

However, the key aspect of this paper is to devise general 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 applications in optimization under uncertainty.

REFERENCES

• 1: Barbara M. Anthony , Vineet Goyal , Anupam Gupta , Viswanath Nagarajan, A plant location guide for the unsure, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1164-1173, January 20-22, 2008, San Francisco, California
• 2: Vijay Arya , Naveen Garg , Rohit Khandekar , Adam Meyerson , Kamesh Munagala , Vinayaka Pandit, Local Search Heuristics for k-Median and Facility Location Problems, SIAM Journal on Computing, v.33 n.3, p.544-562, 2004 [doi>10.1137/S0097539702416402]
• 3: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 4: Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
• 5: Moses Charikar , Samir Khuller , David M. Mount , Giri Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.642-651, January 07-09, 2001, Washington, D.C., United States
• 6: Graham Cormode , Andrew McGregor, Approximation algorithms for clustering uncertain data, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376944]
• 7: Brian C. Dean , Michel X. Goemans , Jan Vondrak, Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.208-217, October 17-19, 2004 [doi>10.1109/FOCS.2004.15]
• 8: Brian C. Dean , Michel X. Goemans , Jan Vondrák, Adaptivity and approximation for stochastic packing problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
• 10: A. Goel, S. Guha, and K. Munagala. How to probe for an extreme value. ACM Trans. Algorithms (to appear), 2008. Preliminary version appeared in Proc. of the ACM Symp. on Principles of Database Systems (PODS), 2006.
• 11: Ashish Goel , Piotr Indyk, Stochastic Load Balancing and Related Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.579, October 17-18, 1999
• 12: Sudipto Guha , Kamesh Munagala, Model-driven optimization using adaptive probes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.308-317, January 07-09, 2007, New Orleans, Louisiana
• 13: Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007419]
• 14: A. Gupta and M. Pál. Stochastic steiner trees without a root. Proc. of ICALP, pages 1051--1063, 2005.
• 15: A. Gupta, M. Pál, R. Ravi, and A. Sinha. What about wednesday? Approximation algorithms for multistage stochastic optimization. Proc. of APPROX-RANDOM, pages 86--98, 2005.
• 16: Anupam Gupta , R. Ravi , Amitabh Sinha, An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.218-227, October 17-19, 2004 [doi>10.1109/FOCS.2004.11]
• 17: D. Hochbaum and D. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180--184, May 1985.
• 18: Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 19: Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001 [doi>10.1145/375827.375845]
• 20: Jon Kleinberg , Yuval Rabani , Éva Tardos, Allocating Bandwidth for Bursty Connections, SIAM Journal on Computing, v.30 n.1, p.191-217, 2000 [doi>10.1137/S0097539797329142]
• 21: A. Krause and C. Guestrin. Near-optimal nonmyopic value of information in graphical models. Twenty-first Conference on Uncertainty in Artificial Intelligence (UAI 2005), 2005.
• 22: Rolf H. Möhring , Andreas S. Schulz , Marc Uetz, Approximation in stochastic scheduling: the power of LP-based priority policies, Journal of the ACM (JACM), v.46 n.6, p.924-942, Nov. 1999 [doi>10.1145/331524.331530]
• 23: David B. Shmoys , Chaitanya Swamy, Stochastic Optimization is (Almost) as easy as Deterministic Optimization, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.228-237, October 17-19, 2004 [doi>10.1109/FOCS.2004.62]
• 24: Martin Skutella , Marc Uetz, Scheduling precedence-constrained jobs with stochastic processing times on parallel machines, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.589-590, January 07-09, 2001, Washington, D.C., United States
• 25: Chaitanya Swamy , David B. Shmoys, Sampling-based Approximation Algorithms for Multi-stage Stochastic, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.357-366, October 23-25, 2005 [doi>10.1109/SFCS.2005.67]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, clustering