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

Dennis Cheung; Felipe Cucker

doi:10.1007/s10107-003-0393-7

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

Dennis Cheung, Felipe Cucker

Department of Mathematics

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

10 Citations (Scopus)

Abstract

We define a condition number script K sign (A,b,c) for a linear program min c_T 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.

Original language	English
Pages (from-to)	175-196
Journal	Mathematical Programming
Volume	99
Issue number	1
DOIs	https://doi.org/10.1007/s10107-003-0393-7
Publication status	Published - Jan 2004

Access Output

10.1007/s10107-003-0393-7

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{5f3b99c4299b44d2a14e803f7a646476,

title = "Solving linear programs with finite precision: I. Condition numbers and random programs",

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. {\textcopyright} Springer-Verlag 2003.",

author = "Dennis Cheung and Felipe Cucker",

year = "2004",

month = jan,

doi = "10.1007/s10107-003-0393-7",

language = "English",

volume = "99",

pages = "175--196",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1",

}

TY - JOUR

T1 - Solving linear programs with finite precision

T2 - I. Condition numbers and random programs

AU - Cheung, Dennis

AU - Cucker, Felipe

PY - 2004/1

Y1 - 2004/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=18144418311&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-18144418311&origin=recordpage

U2 - 10.1007/s10107-003-0393-7

DO - 10.1007/s10107-003-0393-7

M3 - RGC 21 - Publication in refereed journal

SN - 0025-5610

VL - 99

SP - 175

EP - 196

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -

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

Abstract

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this