# Using the Johnson-Lindenstrauss lemma in linear and integer programming

arXiv: https://arxiv.org/abs/1507.00990 · HTML: https://mlsanity.com/paper/1507.00990/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2015.

## Built on by (most cited first, 1 of 1)

- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)

## Abstract (arXiv)

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.