Coverage processes on spheres and condition numbers for linear programming

DOI10.1214/09-AOP489zbMath1205.60027arXiv0712.2816OpenAlexW3098696827WikidataQ57733121 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 programmingcondition numbersgeometric probabilitycoverage processesspherical caps

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Linear programming (90C05) Random convex sets and integral geometry (aspects of convex geometry) (52A22)

Related Items

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

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