Dipartimento di Ingegneria informatica, automatica e gestionale

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