Using the Johnson-Lindenstrauss lemma in linear and integer programming

Ky Vu(vulix.polytechnique.fr)
Pierre-Louis Poirion(poirionlix.polytechnique.fr)
Leo Liberti(libertilix.polytechnique.fr)

Abstract: The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this paper we introduce a first attempt at using this lemma in the context of feasibility problems in linear and integer programming, which cannot be expressed only in function of Euclidean distances.

Keywords: random projections, dimension reduction, cone membership, linear membership

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Working paper, Ecole Polytechnique, June 2015

Download: [PDF]

Entry Submitted: 07/02/2015
Entry Accepted: 07/02/2015
Entry Last Modified: 07/02/2015

Modify/Update this entry