On the average condition of random linear programs

Dennis Cheung; Felipe Cucker

doi:10.1137/120869390

On the average condition of random linear programs

Dennis Cheung
, Felipe Cucker

Department of Mathematics

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

1 Citation (Scopus)

21 Downloads (CityUHK Scholars)

Abstract

We give an O(log n) bound for the expectation of the logarithm of the condition number K(A, b, c) introduced in "Solving Linear Programs with Finite Precision: I. Condition Numbers and Random Programs" [Math. Program., 99 (2004), pp. 175-196]. This bound improves the previously existing bound, which was of O(n), and yields average-case bounds for both the required precision and the complexity of computing an optimal basis (or a pair of primal-dual optimizers). © 2013 Society for Industrial and Applied Mathematics.

Original language	English
Pages (from-to)	799-810
Journal	SIAM Journal on Optimization
Volume	23
Issue number	2
Online published	23 Apr 2013
DOIs	https://doi.org/10.1137/120869390
Publication status	Published - 2013

Research Keywords

Average-case analysis
Conditioning
Linear programming

Publisher's Copyright Statement

COPYRIGHT TERMS OF DEPOSITED FINAL PUBLISHED VERSION FILE: © 2013 Society for Industrial and Applied Mathematics

Access Output

10.1137/120869390

5809935.pdfFinal Published version, 227 KB

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{00b8fbd1581b4be198e970db99cb0e1d,

title = "On the average condition of random linear programs",

abstract = "We give an O(log n) bound for the expectation of the logarithm of the condition number K(A, b, c) introduced in {"}Solving Linear Programs with Finite Precision: I. Condition Numbers and Random Programs{"} [Math. Program., 99 (2004), pp. 175-196]. This bound improves the previously existing bound, which was of O(n), and yields average-case bounds for both the required precision and the complexity of computing an optimal basis (or a pair of primal-dual optimizers). {\textcopyright} 2013 Society for Industrial and Applied Mathematics.",

keywords = "Average-case analysis, Conditioning, Linear programming",

author = "Dennis Cheung and Felipe Cucker",

year = "2013",

doi = "10.1137/120869390",

language = "English",

volume = "23",

pages = "799--810",

journal = "SIAM Journal on Optimization",

issn = "1052-6234",

publisher = "Society for Industrial and Applied Mathematics",

number = "2",

}

TY - JOUR

T1 - On the average condition of random linear programs

AU - Cheung, Dennis

AU - Cucker, Felipe

PY - 2013

Y1 - 2013

N2 - We give an O(log n) bound for the expectation of the logarithm of the condition number K(A, b, c) introduced in "Solving Linear Programs with Finite Precision: I. Condition Numbers and Random Programs" [Math. Program., 99 (2004), pp. 175-196]. This bound improves the previously existing bound, which was of O(n), and yields average-case bounds for both the required precision and the complexity of computing an optimal basis (or a pair of primal-dual optimizers). © 2013 Society for Industrial and Applied Mathematics.

AB - We give an O(log n) bound for the expectation of the logarithm of the condition number K(A, b, c) introduced in "Solving Linear Programs with Finite Precision: I. Condition Numbers and Random Programs" [Math. Program., 99 (2004), pp. 175-196]. This bound improves the previously existing bound, which was of O(n), and yields average-case bounds for both the required precision and the complexity of computing an optimal basis (or a pair of primal-dual optimizers). © 2013 Society for Industrial and Applied Mathematics.

KW - Average-case analysis

KW - Conditioning

KW - Linear programming

UR - https://www.scopus.com/pages/publications/84880753864

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

U2 - 10.1137/120869390

DO - 10.1137/120869390

M3 - RGC 21 - Publication in refereed journal

SN - 1052-6234

VL - 23

SP - 799

EP - 810

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 2

ER -

On the average condition of random linear programs

Abstract

Research Keywords

Publisher's Copyright Statement

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this