Access the full text.
Sign up today, get DeepDyve free for 14 days.
H. Moulin, S. Shenker (2001)
Strategyproof sharing of submodular costs:budget balance versus efficiencyEconomic Theory, 18
András Prékopa (1995)
Stochastic ProgrammingOptimizations and Programming
K. Jain, V. Vazirani (2002)
Equitable cost allocations via primal-dual-type algorithms
W. Haneveld, M. Vlerk (1999)
Stochastic integer programming:General models and algorithmsAnnals of Operations Research, 85
A Proofs from Section 5
J. Kleinberg, Y. Rabani, É. Tardos (1997)
Allocating bandwidth for bursty connectionsSIAM J. Comput., 30
K. Jain, V. Vazirani (2001)
Applications of approximation algorithms to cooperative games
E. Beale (1955)
ON MINIMIZING A CONVEX FUNCTION SUBJECT TO LINEAR INEQUALITIESJournal of the royal statistical society series b-methodological, 17
Anupam Gupta, Amit Kumar, Tim Roughgarden
Simpler and Better Approximation Algorithms for Network Design
(1996)
and M
Martin Pál, É. Tardos (2003)
Group strategy proof mechanisms via primal-dual algorithms44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
W. Sharkey (1996)
Cost allocation
R. Ravi, Amitabh Sinha (2004)
Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization ProblemsMathematical Programming, 108
G. Dantzig (2004)
Linear Programming Under UncertaintyManag. Sci., 50
Theorem 5.1. The cost sharing function ξ given by Pál and Tardos is 5.45-strict for the 3-approximation algorithm of Mettu and Plaxton. Hence, there is a 8.45-approximation algorithm for Stoc
M. Skutella, M. Uetz (2001)
Scheduling precedence-constrained jobs with stochastic processing times on parallel machines
A.1 Facility Location: Strict Cost Shares
Michael Pinedo (1994)
Scheduling: Theory, Algorithms, and Systems
R. Schultz, L. Stougie, Van Vlerk (1996)
Two-stage stochastic integer programming : a surveyStatistica Neerlandica, 50
Beale E. M. L.
173J. Roy. Statist. Soc. Ser. B., 17
Nicole Immorlica, David Karger, M. Minkoff, V. Mirrokni (2004)
On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems
R. Prim (1957)
Shortest connection networks and some generalizationsBell System Technical Journal, 36
Ashish Goel, P. Indyk (1999)
Stochastic load balancing and related problems40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)
David Karger, M. Minkoff (2000)
Building Steiner trees with incomplete global knowledgeProceedings 41st Annual Symposium on Foundations of Computer Science
G. Pillo, F. Archetti (1986)
Stochastic Programming
A. Geller, R. Schmidgall (1980)
Cost AllocationCornell Hotel and Restaurant Administration Quarterly, 21
Anupam Gupta, Amit Kumar, Martin Pál, T. Roughgarden (2003)
Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
G. Robins, A. Zelikovsky (2000)
Improved Steiner tree approximation in graphs
R. Möhring, Andreas Schulz, M. Uetz (1999)
Approximation in stochastic scheduling: the power of LP-based priority policiesJ. ACM, 46
Ramgopal Mettu, C. Plaxton (1999)
The online median problemProceedings 41st Annual Symposium on Foundations of Computer Science
Boosted Sampling: Approximation Algorithms for Stochastic Optimization Anupam Gupta — Martin Pal R. Ravi ¡ Amitabh Sinha ¡ ABSTRACT Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satis es requirements of clients. In the S TEINER T REE problem, for example, edges must be chosen to connect terminals (clients); in V ERTEX C OVER, vertices must be chosen to cover edges (clients); in FACILITY L OCATION, 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 rst stage. The actual requirements are then revealed, drawn from a pre-speci ed 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 rst 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
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.