Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Boosted sampling: approximation algorithms for stochastic optimization

Boosted sampling: approximation algorithms for stochastic optimization 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 http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Boosted sampling: approximation algorithms for stochastic optimization

Association for Computing Machinery — Jun 13, 2004

Loading next page...
 
/lp/association-for-computing-machinery/boosted-sampling-approximation-algorithms-for-stochastic-optimization-KlMKDzxlmt

References (30)

Datasource
Association for Computing Machinery
Copyright
Copyright © 2004 by ACM Inc.
ISBN
1-58113-852-0
doi
10.1145/1007352.1007419
Publisher site
See Article on Publisher Site

Abstract

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

There are no references for this article.