- | ||||
|
![]()
|
Using the Johnson-Lindenstrauss lemma in linear and integer programming
Ky Vu(vu 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |