TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Martin Lotz

Inhalt des Dokuments

zur Navigation

Ehemalige Mitarbeiter

Prof. Dr. Martin Lotz


Mathematics Institute
Zeeman Building
University of Warwick
Coventry CV4 7AL
United Kingdom
Persönliche Homepage

Publikationen in der Arbeitsgruppe

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