skip to main content
10.1145/1007352.1007419acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Boosted sampling: approximation algorithms for stochastic optimization

Published: 13 June 2004 Publication History

Abstract

Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the Steiner Tree problem, for example, edges must be chosen to connect terminals (clients); in Vertex Cover, vertices must be chosen to cover edges (clients); in Facility Location, facilities must be chosen and demand vertices (clients) connected to these chosen facilities. We consider a stochastic version of such a problem where the solution is constructed in two stages: Before the actual requirements materialize, we can choose elements in a first stage. The actual requirements are then revealed, drawn from a pre-specified probability distribution π thereupon, some more elements may be chosen to obtain a feasible solution for the actual requirements. However, in this second (recourse) stage, choosing an element is costlier by a factor of σ> 1. The goal is to minimize the first stage cost plus the expected second stage cost.We give a general yet simple technique to adapt approximation algorithms for several deterministic problems to their stochastic versions via the following method. First stage: Draw σ independent sets of clients from the distribution π and apply the approximation algorithm to construct a feasible solution for the union of these sets. Second stage: Since the actual requirements have now been revealed, augment the first-stage solution to be feasible for these requirements. We use this framework to derive constant factor approximations for stochastic versions of Vertex Cover, Steiner Tree and Uncapacitated Facility Location for arbitrary distributions π in one fell swoop. For special (product) distributions, we obtain additional and improved results. Our techniques adapt and use the notion of strict cost-shares introduced in [5].

References

[1]
E. M. L. Beale. On minimizing a convex function subject to linear inequalities. J. Roy. Statist. Soc. Ser. B., 17:173--184; discussion, 194--203, 1955. (Symposium on linear programming. ).
[2]
John R. Birge and François Louveaux Introduction to stochastic programming. Springer Series in Operations Research. Springer-Verlag, New York, 1997.
[3]
George B. Dantzig. Linear programming under uncertainty. Management Sci., 1:197--206, 1955.
[4]
Ashish Goel and Piotr Indyk. Stochastic load balancing and related problems. In 40th Annual Symposium on Foundations of Computer Science (New York, 1999), pages 579--586. IEEE Computer Soc., Los Alamitos, CA, 1999.
[5]
Anupam Gupta, Amit Kumar, Martin Pál, and Tim Roughgarden. Approximations via cost-sharing. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 606--615, 2003.
[6]
Anupam Gupta, Amit Kumar, and Tim Roughgarden. Simpler and better approximation algorithms for network design. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 365--372, 2003.
[7]
Nicole Immorlica, David Karger, Maria Minkoff, and Vahab Mirrokni. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 684--693, 2004.
[8]
Kamal Jain and Vijay Vazirani. Applications of approximation algorithms to cooperative games. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC), pages 364--372, 2001.
[9]
Kamal Jain and Vijay V. Vazirani. Equitable cost allocations via primal-dual-type algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 313--321. ACM Press, 2002.
[10]
Peter Kall and Stein W. Wallace. Stochastic programming. Wiley-Interscience Series in Systems and Optimization. John Wiley & Sons Ltd., Chichester, 1994.
[11]
David R. Karger and Maria Minkoff. Building Steiner trees with incomplete global knowledge. In Proceedings of the 41th Annual IEEE Symposium on Foundations of Computer Science, pages 613--623, 2000.
[12]
Willem K. Klein Haneveld and Maarten H. van der Vlerk. Stochastic integer programming: general models and algorithms. Ann. Oper. Res., 85:39--57, 1999. Stochastic programming. State of the art, 1998 (Vancouver, BC).
[13]
Willem K. Klein Haneveld and Maarten H. van der Vlerk. Stochastic Programming. Department of Econometrics and OR, University of Groningen, Netherlands, 2003.
[14]
Jon Kleinberg, Yuval Rabani, and Éva Tardos. Allocating bandwidth for bursty connections. SIAM J. Comput., 30(1):191--217 (electronic), 2000.
[15]
Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. In 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000), pages 339--348. IEEE Comput. Soc. Press, Los Alamitos, CA, 2000.
[16]
Rolf H. Möhring, Andreas S. Schulz, and Marc Uetz. Approximation in stochastic scheduling: the power of lp-based priority policies. Journal of the ACM (JACM), 46(6):924--942, 1999.
[17]
Hervé Moulin and Scott Shenker. Strategyproof sharing of submodular costs: budget balance versus efficiency. Econom. Theory, 18(3):511--533, 2001.
[18]
Martin Pál and Éva Tardos. Group strategyproof mechanisms via primal-dual algorithms. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 584--593, 2003.
[19]
Michael Pinedo. Scheduling: Theory, Algorithms, and Systems. Prentice Hall, 1995.
[20]
Robert C. Prim. Shortest interconnection networks and some generalizations. Bell System Technical Journal, 36:1389--1401, 1957.
[21]
R. Ravi and Amitabh Sinha. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In Proceedings of the 10th Integer Programming and Combinatorial Optimization Conference, 2004. To appear.
[22]
Gabriel Robins and Alexander Zelikovsky. Improved Steiner tree approximation in graphs. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 770--779, 2000.
[23]
R. Schultz, L. Stougie, and M. H. van der Vlerk. Two-stage stochastic integer programming: a survey. Statist. Neerlandica, 50(3):404--416, 1996.
[24]
Martin Skutella and Marc Uetz. Scheduling precedence-constrained jobs with stochastic processing times on parallel machines. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 589--590. Society for Industrial and Applied Mathematics, 2001.
[25]
H. P. Young. Cost allocation. In R. J. Aumann and S. Hart, editors, Handbook of Game Theory, volume 2, chapter 34, pages 1193--1235. North-Holland, 1994.

Cited By

View all
  • (2024)Stochastic Optimization and Learning for Two-Stage Supplier ProblemsACM Transactions on Probabilistic Machine Learning10.1145/36046191:1(1-20)Online publication date: 9-Dec-2024
  • (2023)Universal Algorithms for Clustering ProblemsACM Transactions on Algorithms10.1145/357284019:2(1-46)Online publication date: 9-Mar-2023
  • (2023)An Approximation Algorithm for Stochastic Power Cover ProblemTheoretical Computer Science10.1007/978-981-99-7743-7_6(96-106)Online publication date: 26-Nov-2023
  • Show More Cited By

Index Terms

  1. Boosted sampling: approximation algorithms for stochastic optimization

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing
    June 2004
    660 pages
    ISBN:1581138520
    DOI:10.1145/1007352
    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]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 13 June 2004

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. approximation algorithms
    2. boosted sampling
    3. cost sharing
    4. stochastic optimization

    Qualifiers

    • Article

    Conference

    STOC04
    Sponsor:
    STOC04: Symposium of Theory of Computing 2004
    June 13 - 16, 2004
    IL, Chicago, USA

    Acceptance Rates

    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)14
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 15 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Stochastic Optimization and Learning for Two-Stage Supplier ProblemsACM Transactions on Probabilistic Machine Learning10.1145/36046191:1(1-20)Online publication date: 9-Dec-2024
    • (2023)Universal Algorithms for Clustering ProblemsACM Transactions on Algorithms10.1145/357284019:2(1-46)Online publication date: 9-Mar-2023
    • (2023)An Approximation Algorithm for Stochastic Power Cover ProblemTheoretical Computer Science10.1007/978-981-99-7743-7_6(96-106)Online publication date: 26-Nov-2023
    • (2022)Optimization of relay placement for scalable virtual private LAN servicesProceedings of the ACM SIGCOMM Workshop on Future of Internet Routing & Addressing10.1145/3527974.3545719(43-49)Online publication date: 22-Aug-2022
    • (2021)On Stochastic k-Facility LocationAlgorithmic Aspects in Information and Management10.1007/978-3-030-93176-6_5(47-56)Online publication date: 17-Dec-2021
    • (2021)Adaptive Relaxations for Multistage Robust OptimizationPRICAI 2021: Trends in Artificial Intelligence10.1007/978-3-030-89188-6_36(485-499)Online publication date: 25-Oct-2021
    • (2021)On the Power of Static Assignment Policies for Robust Facility Location ProblemsInteger Programming and Combinatorial Optimization10.1007/978-3-030-73879-2_18(252-267)Online publication date: 5-May-2021
    • (2020)Towards an algorithmic synthesis of thermofluid systemsOptimization and Engineering10.1007/s11081-020-09564-1Online publication date: 18-Sep-2020
    • (2020)A Novel Application for Game Tree Search - Exploiting Pruning Mechanisms for Quantified Integer ProgramsAdvances in Computer Games10.1007/978-3-030-65883-0_6(66-78)Online publication date: 20-Dec-2020
    • (2019)Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control ModelsMathematics of Operations Research10.1287/moor.2018.094044:2(668-692)Online publication date: 1-May-2019
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media