research-article

How to probe for an extreme value

Authors:

Kamesh MunagalaAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 7, Issue 1

Article No.: 12, Pages 1 - 20

https://doi.org/10.1145/1868237.1868250

Published: 08 December 2010 Publication History

Abstract

In several systems applications, parameters such as load are known only with some associated uncertainty, which is specified, or modeled, as a distribution over values. The performance of the system optimization and monitoring schemes can be improved by spending resources such as time or bandwidth in observing or resolving the values of these parameters. In a resource-constrained situation, deciding which parameters to observe in order to best optimize the expected system performance (or in general, optimize the expected value of a certain objective function) itself becomes an interesting optimization problem.

In this article, we initiate the study of such problems that we term “model-driven optimization”. In particular, we study the problem of optimizing the minimum value in the presence of observable distributions. We show that this problem is NP-Hard, and present greedy algorithms with good performance bounds. The proof of the performance bounds are via novel sub-modularity arguments and connections to covering integer programs.

References

[1]

Akella, A., Maggs, B. M., Seshan, S., Shaikh, A., and Sitaraman, R. K. 2003. A measurement-based analysis of multihoming. In Proceedings of the ACM SIGCOMM Conference. 353--364.

Digital Library

[2]

Avnur, R., and Hellerstein, J. M. 2000. Eddies: Continuously adaptive query processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'00). 261--272.

Digital Library

[3]

Babcock, B., and Chaudhuri, S. 2005. Towards a robust query optimizer: A principled and practical approach. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'05). 119--130.

Digital Library

[4]

Babcock, B., and Olston, C. 2003. Distributed top-k monitoring. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'03). 28--39.

Digital Library

[5]

Babu, S., Bizarro, P., and DeWitt, D. J. 2005. Proactive reoptimization. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 107--118.

Digital Library

[6]

Carr, R., Fleischer, L., Leung, V., and Phillips, C. 2000. Strengthening integrality gaps for capacitated network design and covering problems. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 106--115.

Digital Library

[7]

Charikar, M., Fagin, R., Kleinberg, J., Raghavan, P., and Sahai, A. 2002. Query strategies for priced information. J. Comput. Syst. Sci 64(4).

Digital Library

[8]

Chu, F., Halpern, J., and Gehrke, J. 2002. Least expected cost query optimization: What can we expect&quest; In Proceedings of the ACM Symposium on Principles of Database Systems (PODS). 293--302.

Digital Library

[9]

Chu, F., Halpern, J., and Seshadri, P. 1999. Least expected cost query optimization: An exercise in utility. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS). 138--147.

Digital Library

[10]

Dean, B., Goemans, M., and Vondrák, J. 2004. Approximating the stochastic knapsack problem: The benefit of adaptivity. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 208--217.

Digital Library

[11]

Deshpande, A., Guestrin, C., Madden, S., Hellerstein, J. M., and Hong, W. 2004. Model-driven data acquisition in sensor networks. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 588--599.

Digital Library

[12]

Feder, T., Motwani, R., Panigrahy, R., Olston, C., and Widom, J. 2003. Computing the median with uncertainty. SIAM J. Comput. 32, 2.

Digital Library

[13]

Goel, A., Guha, S., and Munagala, K. 2006. Asking the right questions: Model-driven optimization using probes. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS). 203--212.

Digital Library

[14]

Goel, A., and Indyk, P. 1999. Stochastic load balancing and related problems. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 579--586.

Digital Library

[15]

Guha, S., and Munagala, K. 2007. Model-driven optimization using adaptive probes. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 308--317.

Digital Library

[16]

Guha, S., and Munagala, K. 2008. Sequential design of experiments via linear programming. Computing Research Repository, arXiv:0805.2630

[17]

Guha, S., Munagala, K., and Sarkar, S. 2008. Information acquisition and exploitation in multi-channel wireless systems. Computing Research Repository, arXiv:0804.1724.

[18]

Gummadi, P. K., Madhyastha, H. V., Gribble, S. D., Levy, H. M. and Wetherall, D. 2004. Improving the reliability of internet paths with one-hop source routing. In Proceedings of the 6th Symposium on Operating System Design and Implementation (OSDI). 183--198.

Digital Library

[19]

Gupta, A., P' al, M., Ravi, R., and Sinha, A. 2004. Boosted sampling: Approximation algorithms for stochastic optimization. In Proceedings of the ACM Symposium on Theory of Computing (STOC). 417--426.

Digital Library

[20]

Gupta, A., Ravi, R., and Sinha, A. 2004. An edge in time saves nine: LP rounding approximation algorithms for stochastic network design. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 218--227.

Digital Library

[21]

Immorlica, N., Karger, D., Minkoff, M., and Mirrokni, V. 2004. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 691--700.

Digital Library

[22]

Khanna, S., and Tan, W-C. 2001. On computing functions with uncertainty. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS).

Digital Library

[23]

Kleinberg, J., Rabani, Y., and Tardos, É. 2000. Allocating bandwidth for bursty connections. SIAM J. Comput. 30(1).

Digital Library

[24]

Kolliopoulos, S., and Young, N. 2001. Tight approximation results for general covering integer programs. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 522--528.

Digital Library

[25]

Krause, A., and Guestrin, C. 2005. Near-optimal nonmyopic value of information in graphical models. In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI). 324--331.

[26]

Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. 1978. An analysis of approximations for maximizing submodular set functions-I. Math Program. 14(1), 265--294.

Digital Library

[27]

Olston, C. 2003. Approximate Replication. Ph.D. dissertatis Stanford Univ.

Digital Library

[28]

Shmoys, D., and Swamy, C. 2004. Stochastic optimization is (almost) as easy as discrete optimization. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 228--237.

Digital Library

[29]

Silberstein, A., Braynard, R., Ellis, C., Munagala, K., and Yang, J. 2006. A sampling based approach to optimizing top-k queries in sensor networks. In Proceedings of the International Conference on Data Engineering (ICDE). 68--77,

Digital Library

Cited By

Papadimitriou CPollner TSaberi AWajc D(2024)Online Stochastic Max-Weight Bipartite MatchingMathematics of Operations Research10.1287/moor.2023.138949:3(1607-1628)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/moor.2023.1389
Lozano LBorrero J(2024)A Bilevel Optimization Approach for a Class of Combinatorial Problems with Disruptions and ProbingINFORMS Journal on Computing10.1287/ijoc.2024.0629Online publication date: 13-Dec-2024
https://doi.org/10.1287/ijoc.2024.0629
Gravin NXu YZhou RChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Bidder Selection Problem in Position Auctions: A Fast and Simple Algorithm via Poisson ApproximationProceedings of the ACM Web Conference 202410.1145/3589334.3645418(89-98)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645418
Show More Cited By

Index Terms

How to probe for an extreme value
1. Mathematics of computing
  1. Probability and statistics
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Apply the Ant Feature of Sensation to Calculate the Minimum Value of Function
ICGEC '10: Proceedings of the 2010 Fourth International Conference on Genetic and Evolutionary Computing

Calculating the minimum (or maximum) value of functions is an important problem in optimization field. Applying the method of ant colony optimization (ACO) to solve the problem is an interesting research topic currently, and the main disadvantage is ...
Self-adaptive velocity particle swarm optimization for solving constrained optimization problems

Particle swarm optimization (PSO) is originally developed as an unconstrained optimization technique, therefore lacks an explicit mechanism for handling constraints. When solving constrained optimization problems (COPs) with PSO, the existing research ...
Particle swarm approach for structural design optimization

This paper presents in detail the background and implementation of a particle swarm optimization algorithm suitable for constraint structural optimization tasks. Improvements, effect of the different setting parameters, and functionality of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 7, Issue 1

November 2010

282 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1868237

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 December 2010

Accepted: 01 August 2008

Revised: 01 August 2008

Received: 01 December 2007

Published in TALG Volume 7, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
412
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)8

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Papadimitriou CPollner TSaberi AWajc D(2024)Online Stochastic Max-Weight Bipartite MatchingMathematics of Operations Research10.1287/moor.2023.138949:3(1607-1628)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/moor.2023.1389
Lozano LBorrero J(2024)A Bilevel Optimization Approach for a Class of Combinatorial Problems with Disruptions and ProbingINFORMS Journal on Computing10.1287/ijoc.2024.0629Online publication date: 13-Dec-2024
https://doi.org/10.1287/ijoc.2024.0629
Gravin NXu YZhou RChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Bidder Selection Problem in Position Auctions: A Fast and Simple Algorithm via Poisson ApproximationProceedings of the ACM Web Conference 202410.1145/3589334.3645418(89-98)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645418
Hoefer MSchewior KSchmand D(2024)Stochastic Probing with Increasing PrecisionSIAM Journal on Discrete Mathematics10.1137/22M149466X38:1(148-169)Online publication date: 8-Jan-2024
https://doi.org/10.1137/22M149466X
Wang HSun QLi QMa XWang S(2024)Online Request Replication for Obtaining Fresh Information Under Pull ModelIEEE Internet of Things Journal10.1109/JIOT.2024.340492011:16(27864-27875)Online publication date: 15-Aug-2024
https://doi.org/10.1109/JIOT.2024.3404920
Fu HLi JLiu DSaha BServedio R(2023)Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation SchemeProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585229(789-802)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585229
Li QMa XZhou AJoo CWang S(2023)Online Service Request Duplicating for Vehicular ApplicationsIEEE Transactions on Mobile Computing10.1109/TMC.2022.314817022:7(4168-4180)Online publication date: 1-Jul-2023
https://doi.org/10.1109/TMC.2022.3148170
Zhou YSun HJin YZhu YLi YQian ZZhang SLu S(2022)Inference replication at edges via combinatorial multi-armed banditJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2022.102636129:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.sysarc.2022.102636
Segev DSingla SBiró PChawla SEchenique F(2021)Efficient Approximation Schemes for Stochastic Probing and Prophet ProblemsProceedings of the 22nd ACM Conference on Economics and Computation10.1145/3465456.3467614(793-794)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3465456.3467614
Sun YZhou SNiu Z(2021)Distributed Task Replication for Vehicular Edge Computing: Performance Analysis and Learning-Based AlgorithmIEEE Transactions on Wireless Communications10.1109/TWC.2020.303088920:2(1138-1151)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1109/TWC.2020.3030889
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents