Coverage processes on spheres and condition numbers for linear programming

Details Coverage processes on spheres and condition numbers for linear programming Coverage processes on spheres and condition numbers for linear programming

2007-12-17

arxiv.org/abs/0712.2816v3

Annals of Probability 2010, Vol. 38, No. 2, 570-604

Mathematics

Probability

Published in at http://dx.doi.org/10.1214/09-AOP489 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of

Scientific paper

10.1214/09-AOP489

This paper has two agendas. Firstly, we exhibit new results for coverage processes. Let $p(n,m,\alpha)$ be the probability that $n$ spherical caps of angular radius $\alpha$ in $S^m$ do not cover the whole sphere $S^m$. We give an exact formula for $p(n,m,\alpha)$ in the case $\alpha\in[\pi/2,\pi]$ and an upper bound for $p(n,m,\alpha)$ in the case $\alpha\in [0,\pi/2]$ which tends to $p(n,m,\pi/2)$ when $\alpha\to\pi/2$. In the case $\alpha\in[0,\pi/2]$ this yields upper bounds for the expected number of spherical caps of radius $\alpha$ that are needed to cover $S^m$. Secondly, we study the condition number ${\mathscr{C}}(A)$ of the linear programming feasibility problem $\exists x\in\mathbb{R}^{m+1}Ax\le0,x\ne0$ where $A\in\mathbb{R}^{n\times(m+1)}$ is randomly chosen according to the standard normal distribution. We exactly determine the distribution of ${\mathscr{C}}(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}(\ln{\mathscr{C}}(A))\le2\ln(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.

Affiliated with

Also associated with

No associations

Rating

Coverage processes on spheres and condition numbers for linear programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Coverage processes on spheres and condition numbers for linear programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coverage processes on spheres and condition numbers for linear programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-548621