Content deleted Content added
Erel Segal (talk | contribs) |
m v2.05b - Bot T12 CW#548 - Fix errors for CW project (Punctuation in link - Link equal to linktext) |
||
Line 270:
* A certificate that there is no feasible solution.
The run-time in the [[Real RAM]] model is, [[
O\left (\frac{N \cdot \log{n}\cdot \log{m} \cdot log(1/\epsilon)}{\epsilon^3}\right)
</math>, where ''N'' is input size (number of nonzero entries in the matrices), ''n'' is the number of variables, and ''m'' is the number of inequality constraints. Note that the runtime is polynomial in 1/''ε'' rather than log(1/''ε''). However, in practice it runs quite fast.
Line 289:
* A certificate that no feasible solution exists.
The run-time in the [[Real RAM]] model is, [[
O\left (\frac{N \cdot \log{n}\cdot \log{m} \cdot }{\epsilon^3}\right)
</math>. The algorithm is applied in a [[binary search]] style to find an approximately-optimal solution.
| |||