Solving linear programs with finite precision : I. Condition numbers and random programs

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

10 Scopus Citations
Scopus Metrics
View graph of relations

Author(s)

  • Dennis Cheung
  • Felipe Cucker

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)175-196
Journal / PublicationMathematical Programming
Volume99
Issue number1
Publication statusPublished - Jan 2004

Link(s)

DOI

DOI
Check@CityULib
Link to Scopus https://www.scopus.com/record/display.uri?eid=2-s2.0-18144418311&origin=recordpage
Permanent Link https://scholars.cityu.edu.hk/en/publications/publication(5f3b99c4-299b-44d2-a14e-803f7a646476).html

Abstract

We define a condition number script K sign (A,b,c) for a linear program min cT x s.t. Ax = b,x ≤ 0 and give two characterizations via distances to degeneracy and singularity. We also give bounds for the expected value, as well as for higher moments, of log script K sign (A,b,c) when the entries of A,b and c are i.i.d. random variables with normal distribution. © Springer-Verlag 2003.

Fingerprint

Publication fingerprints text

100
Linear Program Computer Science
100
Finite Precision Computer Science
100
Condition Number Computer Science
100
Program Computer Science
100
Number Mathematics
100
randomness INIS
100
precision INIS
100
Linear Programming Keyphrases
50
Normal Distribution Computer Science
50
Iid Random Variable Computer Science
Full Fingerprint ›

Citation Format(s)

[ RIS ] [ BibTeX ]
Solving linear programs with finite precision: I. Condition numbers and random programs. / Cheung, Dennis; Cucker, Felipe.
In: Mathematical Programming, Vol. 99, No. 1, 01.2004, p. 175-196.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review