Solving linear programs with finite precision : II. Algorithms

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

12 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)305-335
Journal / PublicationJournal of Complexity
Volume22
Issue number3
Publication statusPublished - Jun 2006

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