Page Content
There is no English translation for this web page.
Prof. Dr. Martin Lotz
[1]- © Martin Lotz
Mathematics Institute
Zeeman Building
University of Warwick
Coventry CV4 7AL
United Kingdom Persönliche Homepage
http://homepages.warwick.ac.uk/staff/Martin.Lotz/ [2]
Publikationen in der Arbeitsgruppe
| 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 $ain [fracpi2,pi]$ and an upper bound for $p(n,m,a)$ in the case $ain [0,fracpi2]$, which tends to $p(n,m,fracpi2)$ when $atofracpi2$. In the case $ain [0,fracpi2]$ 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 xinmathbb R^m+1, Axłe 0,, xne 0$, where $Ainmathbb 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. |
Back [6]
isser/persons/lotz_m.jpg
ublished.pdf
g/fachgebiet_algorithmische_algebra/v_menue/members/dr_
martin_lotz/parameter/en/font4/minhilfe/?no_cache=1&
;tx_sibibtex_pi1%5Bdownload_bibtex_uid%5D=1351093&t
x_sibibtex_pi1%5Bcontentelement%5D=tt_content%3A721951
g/fachgebiet_algorithmische_algebra/v_menue/members/dr_
martin_lotz/parameter/en/font4/minhilfe/
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.
Copyright TU Berlin 2008