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

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

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

Laura Palagi