|
 
|
[LPV16] Solving LP using random projections
Conférence Internationale avec comité de lecture : CTW16, November 2016, pp. Pages 53-56, Italy, (DOI: https://doi.org/10.1016/j.endm.2016.10.014)
motcle:
Résumé:
A celebrated result of Johnson and Lindenstrauss asserts that, in high enough dimensional spaces, Euclidean distances defined by a finite set of points are approximately preserved when these points are projected to a certain lower dimensional space. We show that the distance from a point to a convex set is another approximate invariant, and leverage this result to approximately solve linear programs with a logarithmic number of rows.
BibTeX
| @inproceedings { | |||
| LPV16, | |||
| title | = | "{Solving LP using random projections}", | |
| author | = | " L. Liberti and P. Poirion and Ky Vu ", | |
| booktitle | = | "{CTW16}", | |
| year | = | 2016, | |
| month | = | "November", | |
| pages | = | " Pages 53-56", | |
| address | = | " Italy", | |
| doi | = | "https://doi.org/10.1016/j.endm.2016.10.014", | |
| } | |||
