Model-driven optimization using adaptive probes

ABSTRACT

In several applications such as databases, planning, and sensor networks, parameters such as selectivity, load, or sensed values are known only with some associated uncertainty. The performance of such a system (as captured by some objective function over the parameters) is significantly improved if some of these parameters can be probed or observed. In a resource constrained situation, deciding which parameters to observe in order to optimize system performance itself becomes an interesting and important optimization problem. This problem is the focus of this paper. Unfortunately designing optimal observation schemes is NP-HARD even for the simplest objective functions, leading to the study of approximation algorithms.

In this paper we present general techniques for designing non-adaptive probing algorithms which are at most a constant factor worse than optimal adaptive probing schemes. Interestingly, this shows that for several problems of interest, while probing yields significant improvement in the objective function, being adaptive about the probing is not beneficial beyond constant factors.

REFERENCES

• 1: Aditya Akella , Bruce Maggs , Srinivasan Seshan , Anees Shaikh , Ramesh Sitaraman, A measurement-based analysis of multihoming, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863995]
• 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: Shivnath Babu , Pedro Bizarro , David DeWitt, Proactive re-optimization, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066171]
• 4: Moses Charikar , Ronald Fagin , Venkatesan Guruswami , Jon Kleinberg , Prabhakar Raghavan , Amit Sahai, Query strategies for priced information (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.582-591, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335382]
• 5: 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
• 6: 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]
• 7: 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
• 8: Francis Chu , Joseph Halpern , Johannes Gehrke, Least expected cost query optimization: what can we expect?, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543651]
• 9: Francis Chu , Joseph Y. Halpern , Praveen Seshadri, Least expected cost query optimization: an exercise in utility, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.138-147, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303990]
• 10: 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]
• 11: 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
• 12: Amol Deshpande , Carlos Guestrin , Samuel R. Madden , Joseph M. Hellerstein , Wei Hong, Model-driven data acquisition in sensor networks, Proceedings of the Thirtieth international conference on Very large data bases, p.588-599, August 31-September 03, 2004, Toronto, Canada
• 13: Tomás Feder , Rajeev Motwani , Rina Panigrahy , Chris Olston , Jennifer Widom, Computing the Median with Uncertainty, SIAM Journal on Computing, v.32 n.2, p.538-547, 2003 [doi>10.1137/S0097539701395668]
• 14: Ashish Goel , Sudipto Guha , Kamesh Munagala, Asking the right questions: model-driven optimization using probes, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142380]
• 15: 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
• 16: 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
• 17: S. Guha, K. Munagala, and S. Sarkar. Performance guarantees through partial information based control in multichannel wireless systems. Available at http://www.cs.duke.edu/~kamesh/partialinfo.pdf.
• 18: Krishna P. Gummadi , Harsha V. Madhyastha , Steven D. Gribble , Henry M. Levy , David Wetherall, Improving the reliability of internet paths with one-hop source routing, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.13-13, December 06-08, 2004, San Francisco, CA
• 19: 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]
• 20: A. Gupta and M. Pál. Stochastic steiner trees without a root. Proc. of ICALP, pages 1051--1063, 2005.
• 21: 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.
• 22: 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]
• 23: 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
• 24: 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]
• 25: Sanjeev Khanna , Wang-Chiew Tan, On computing functions with uncertainty, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.171-182, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375577]
• 26: 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]
• 27: 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.
• 28: 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]
• 29: G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-I. Math Programming, 14(1):265--294, 1978.
• 30: Christopher Alden Remi Olston , Jennifer Widom, Approximate replication, Stanford University, Stanford, CA, 2003
• 31: 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]
• 32: 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
• 33: 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]