Home » Node » 12394

MORE@DIAG Seminar: On the approximate solution of large dense Linear Programs

Leo Liberti, CNRS LIX Ecole Polytechnique
Data dell'evento: 
Venerdì, 12 May, 2017 - 15:00
Aula Magna - DIAG
Laura Palagi

A well known lemma by Johnson and Lindenstrauss states that given a finite set X of n points in a Euclidean space E(m) in m dimensions and a small real tolerance 0<t<1, there is a k ~ O(1/t^2 log(n)) and a mapping f:E(m)-->E(k) such that: for each x,y in E(m)   (1-t)||x-y|| <= ||f(x)-f(y)|| <= (1+t)||x-y||.
We apply the Johnson-Lindenstrauss lemma to the columns of a Linear Program (LP), and show that the resulting projected LP approximates the original LP quite well. We showcase the application of this methodology to solving large (and rather dense) LPs.

Joint work with PL Poirion and Vu Khac Ky

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma