Stochastic Combinatorial Optimization under Probabilistic Constraints

Details Stochastic Combinatorial Optimization under Probabilistic Constraints Stochastic Combinatorial Optimization under Probabilistic Constraints

2008-09-02

arxiv.org/abs/0809.0460v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper, we present approximation algorithms for combinatorial optimization problems under probabilistic constraints. Specifically, we focus on stochastic variants of two important combinatorial optimization problems: the k-center problem and the set cover problem, with uncertainty characterized by a probability distribution over set of points or elements to be covered. We consider these problems under adaptive and non-adaptive settings, and present efficient approximation algorithms for the case when underlying distribution is a product distribution. In contrast to the expected cost model prevalent in stochastic optimization literature, our problem definitions support restrictions on the probability distributions of the total costs, via incorporating constraints that bound the probability with which the incurred costs may exceed a given threshold.

Affiliated with

Also associated with

No associations

Rating

Stochastic Combinatorial Optimization under Probabilistic Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stochastic Combinatorial Optimization under Probabilistic Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stochastic Combinatorial Optimization under Probabilistic Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-61331