Optimization Online


Using the Johnson-Lindenstrauss lemma in linear and integer programming

Ky Vu(vu***at***lix.polytechnique.fr)
Pierre-Louis Poirion(poirion***at***lix.polytechnique.fr)
Leo Liberti(liberti***at***lix.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society