direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

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
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

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.