TU Berlin

Fachgebiet Algorithmische AlgebraJournal Publications

Page Content

to Navigation

There is no English translation for this web page.

Journal Publications

Coverage Processes on Spheres and Condition Numbers for Linear Programming
Citation key BCL-Coverage-Processes-On-Spheres-And-Condition-Numbers-For-Linear-Programming
Author Peter Bürgisser and Felipe Cucker and Martin Lotz
Pages 570-604
Year 2010
ISSN 0091-1798
DOI 10.1214/09-AOP489
Journal The Annals of Probability
Volume 38
Number 2
Abstract This paper has two agendas. Firstly, we exhibit new results for coverage processes. Let $p(n,m,a)$ be the probability that n spherical caps of angular radius $a$ in $S^m$ do not cover the whole sphere $S^m$. We give an exact formula for $p(n,m,a)$ in the case $a\in [\frac\pi2,\pi]$ and an upper bound for $p(n,m,a)$ in the case $a\in [0,\frac\pi2]$, which tends to $p(n,m,\frac\pi2)$ when $a\to\frac\pi2$. In the case $a\in [0,\frac\pi2]$ this yields upper bounds for the expected number of spherical caps of radius $a$ that are needed to cover $S^m$. Secondly, we study the condition number $CC(A)$ of the linear programming feasibility problem $\exists x\in\mathbb R^m+1\, Axłe 0,\, x\ne 0$, where $A\in\mathbb R^n× (m+1)$ is randomly chosen according to the standard normal distribution. We exactly determine the distribution of $CC(A)$ conditioned to $A$ being feasible and provide an upper bound on the distribution function in the infeasible case. Using these results, we show that $\mathbf E(łn CC(A))łe 2łn(m+1) + 3.31$ for all $n>m$, the sharpest bound for this expectancy as of today. Both agendas are related through a result which translates between coverage and condition.
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe