Solving linear programs with finite precision : II. Algorithms
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 305-335 |
| Journal / Publication | Journal of Complexity |
| Volume | 22 |
| Issue number | 3 |
| Publication status | Published - Jun 2006 |
Link(s)
Abstract
We describe an algorithm that first decides whether the primal-dual pair of linear programs{A formula is presented}is feasible and in case it is, computes an optimal basis and optimal solutions. Here, A ∈ Rm × n, b ∈ Rm, c ∈ Rn are given. Our algorithm works with finite precision arithmetic. Yet, this precision is variable and is adjusted during the algorithm. Both the finest precision required and the complexity of the algorithm depend on the dimensions n and m as well as on the condition K ( A, b, c ) introduced in D. Cheung and F. Cucker [Solving linear programs with finite precision: I. Condition numbers and random programs, Math. Program. 99 (2004) 175-196]. © 2005 Elsevier Inc. All rights reserved.
Research Area(s)
- Conditioning, Finite precision, Linear programming
Citation Format(s)
Solving linear programs with finite precision: II. Algorithms. / Cheung, Dennis; Cucker, Felipe.
In: Journal of Complexity, Vol. 22, No. 3, 06.2006, p. 305-335.
In: Journal of Complexity, Vol. 22, No. 3, 06.2006, p. 305-335.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
