Coverage processes on spheres and condition numbers for linear programming

DOI10.1214/09-AOP489zbMath1205.60027arXiv0712.2816WikidataQ57733121 ScholiaQ57733121MaRDI QIDQ964778

Martin Lotz, Felipe Cucker, Peter Bürgisser

Publication date: 21 April 2010

Published in: The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

linear programming; condition numbers; geometric probability; coverage processes; spherical caps

Mathematics Subject Classification ID

60D05: Geometric probability and stochastic geometry

90C05: Linear programming

52A22: Random convex sets and integral geometry (aspects of convex geometry)

Related Items

A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, On the volume of tubular neighborhoods of real algebraic varieties, Asymptotic Methods for Random Tessellations, Random Point Sets on the Sphere—Hole Radii, Covering, and Separation, Probabilistic analyses of condition numbers, Computational performance of a projection and rescaling algorithm, Error bounds for consistent reconstruction: random polytopes and coverage processes, Robust smoothed analysis of a condition number for linear programming, From Steiner formulas for cones to concentration of intrinsic volumes, Computational complexity of kernel-based density-ratio estimation: a condition number analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smoothed analysis of condition numbers and complexity implications for linear programming
• Robust smoothed analysis of a condition number for linear programming
• Probabilistic analysis of condition numbers for linear programming
• Conditioning of random conic systems under a general family of input distributions
• On the coverage of k-dimensional space by k-dimensional spheres
• Random coverings in several dimensions
• Asymptotic coverage distributions on the circle
• On the expected condition number of linear programming problems
• Random points on the boundary of smooth convex bodies
• A Primal-Dual Algorithm for Solving Polyhedral Conic Systems with a Finite-Precision Machine
• ON COVERING A CIRCLE BY RANDOMLY PLACED ARCS
• Random circles on a sphere
• A Problem in Geometric Probability.
• The Relaxation Method for Solving Systems of Linear Inequalities
• Covering the circle with random arcs of random sizes
• A Kinematic Formula and Moment Measures of Random Sets
• Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems
• The probability of covering a sphere with N circular caps
• The Cauchy–Poisson problem for a viscous liquid
• The asymptotic values of certain coverage probabilities
• Isotropic random simplices
• SOLUTION TO A GEOMETRICAL PROBLEM IN PROBABILITY
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• A new condition number for linear programming