TU Berlin

Fachgebiet Algorithmische AlgebraJournal Publications

Inhalt des Dokuments

zur Navigation

Journal Publications

Coverage Processes on Spheres and Condition Numbers for Linear Programming
Zitatschlüssel BCL-Coverage-Processes-On-Spheres-And-Condition-Numbers-For-Linear-Programming
Autor Peter Bürgisser and Felipe Cucker and Martin Lotz
Seiten 570-604
Jahr 2010
ISSN 0091-1798
DOI 10.1214/09-AOP489
Journal The Annals of Probability
Jahrgang 38
Nummer 2
Zusammenfassung 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 zur Publikation Link zur Originalpublikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe