Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
From MaRDI portal
Abstract: We consider the stochastic geometry model where the location of each node is a random point in a given metric space, or the existence of each node is uncertain. We study the problems of computing the expected lengths of several combinatorial or geometric optimization problems over stochastic points, including closest pair, minimum spanning tree, -clustering, minimum perfect matching, and minimum cycle cover. We also consider the problem of estimating the probability that the length of closest pair, or the diameter, is at most, or at least, a given threshold. Most of the above problems are known to be -hard. We obtain FPRAS (Fully Polynomial Randomized Approximation Scheme) for most of them in both the existential and locational uncertainty models. Our result for stochastic minimum spanning trees in the locational uncertain model improves upon the previously known constant factor approximation algorithm. Our results for other problems are the first known to the best of our knowledge.
Recommendations
- Approximation algorithms for stochastic combinatorial optimization problems
- Stochastic combinatorial optimization via Poisson approximation
- Maximizing expected utility for stochastic combinatorial optimization problems
- Approximation algorithms for reliable stochastic combinatorial optimization
- Approximative solutions of stochastic optimization problems
- Approximations for Probability Distributions and Stochastic Optimization Problems
- scientific article; zbMATH DE number 2169759
- Approximation of stochastic programming problems
- Probabilistic asymptotic properties of some combinatorial optimization problems
- Probabilistic Combinatorial Optimization: Moments, Semidefinite Programming, and Asymptotic Bounds
Cites work
- (Approximate) uncertain skylines
- A Priori Bounds on the Euclidean Traveling Salesman
- An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
- Approximating the statistics of various properties in randomly weighted graphs
- Approximation Algorithms for 2-Stage Stochastic Optimization Problems
- Closest pair and the post office problem for stochastic points
- How Long Can a Euclidean Traveling Salesman Tour Be?
- scientific article; zbMATH DE number 1444281 (Why is no real title available?)
- scientific article; zbMATH DE number 3193293 (Why is no real title available?)
- Lectures on stochastic programming. Modeling and theory.
- Nearest-neighbor searching under uncertainty. I
- On Frieze's (3) limit for lengths of minimal spanning trees
- On the value of a random minimum spanning tree problem
- Probabilistic databases
- Range searching on uncertain data
- Shape Fitting on Point Sets with Probability Distributions
- Stochastic minimum spanning trees in Euclidean spaces
- The capacity of wireless networks
- The union of probabilistic boxes: Maintaining the volume
Cited in
(9)- More efficient algorithms for stochastic diameter and some unapproximated problems in metric space
- Combinatorial Optimization Over Two Random Point Sets
- Closest pair and the post office problem for stochastic points
- Computing the Expected Value and Variance of Geometric Measures
- Stochastic \(k\)-center and \(j\)-flat-center problems
- Approximating the distribution of the median and other robust estimators on uncertain data
- Closest pair and the post office problem for stochastic points
- Maximizing expected utility for stochastic combinatorial optimization problems
- Stochastic minimum spanning trees in Euclidean spaces
This page was built for publication: Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448848)
