Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points

DOI10.1007/978-3-662-47672-7_74zbMath1440.68333arXiv1209.5828OpenAlexW1514180083MaRDI QIDQ3448848

Lingxiao Huang, Jian Li

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1209.5828

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

Computing the Expected Value and Variance of Geometric Measures ⋮ Unnamed Item ⋮ Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems ⋮ On the expected diameter, width, and complexity of a stochastic convex hull

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• (Approximate) uncertain skylines
• Closest pair and the post office problem for stochastic points
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
• Range queries on uncertain data
• On the value of a random minimum spanning tree problem
• On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees
• Convex hulls under uncertainty
• Nearest-neighbor searching under uncertainty. I
• The Union of Probabilistic Boxes: Maintaining the Volume
• Probabilistic Databases
• Range searching on uncertain data
• Shape Fitting on Point Sets with Probability Distributions
• The capacity of wireless networks
• How Long Can a Euclidean Traveling Salesman Tour Be?
• A Priori Bounds on the Euclidean Traveling Salesman
• Approximation Algorithms for 2-Stage Stochastic 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