Coverage processes on spheres and condition numbers for linear programming (Q964778): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3098696827 / rank | |||
Normal rank |
Latest revision as of 09:45, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Coverage processes on spheres and condition numbers for linear programming |
scientific article |
Statements
Coverage processes on spheres and condition numbers for linear programming (English)
0 references
21 April 2010
0 references
Let \(p(n,m,\alpha)\) be the probability that \(n\) spherical caps of angular radius \(\alpha\) do not cover the whole sphere \(S^m\). The authors give an exact formula for this probability in the case \(\alpha\in[\pi/2,\pi]\) and an upper bound in the case \(\alpha\in[0,\pi/2]\), which tends to the exact value as \(\alpha\to\pi/2\). The obtained upper bound yields upper bounds for the expected number of caps that are needed to cover the whole sphere. Then the authors study the condition number \(\mathcal{C}(A)\) of the linear programming feasibility problem concerning the existence of a nonzero \(x\in\mathbb{R}^{m+1}\) such that \(Ax\leq 0\) componentwise, where a \(n\times(m+1)\) matrix \(A\) is randomly chosen according to the standard normal distribution. The relation to spherical caps is explained by the fact that \(\mathcal{C}(A)\) equals \(1/|\cos\rho(A)|\), where \(\rho(A)\) is the radius of a largest excluding cap for \(A=(a_1,\dots,a_n)\), i.e. the complement to the smallest cap that contains the points \(a_1,\dots,a_n\). The authors exactly determine the distribution of \(\mathcal{C}(A)\) conditioned on \(A\) being feasible and provide an upper bound on the distribution function in the infeasible case. From these results they show that \[ \mathbf{E} \ln\mathcal{C}(A)\leq 2 \ln(m+1)+3.31\,,\quad n>m\,, \] which is the sharpest known bound for this expectation.
0 references
condition numbers
0 references
coverage processes
0 references
geometric probability
0 references
linear programming
0 references
spherical caps
0 references
0 references
0 references