Random Projections for Linear Programming

DOI10.1287/moor.2017.0894zbMath1440.90024arXiv1706.02768OpenAlexW2621792434MaRDI QIDQ5219688

Pierre-Louis Poirion, Leo Liberti, K. H. Vu

Publication date: 12 March 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.02768

zbMATH Keywords

dimension reductionconcentration of measureJohnson-Lindenstrauss lemma

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Linear programming (90C05) Asymptotic theory of convex bodies (52A23)

Related Items

Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections, Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds, Convexification with Bounded Gap for Randomly Projected Quadratic Optimization, Distance geometry and data science, Stable probability of reduced matrix obtained by Gaussian random projection, Random projections for quadratic programs, Global optimization using random embeddings, Simple and fast algorithm for binary integer and online linear programming, Bound-constrained global optimization of functions with low effective dimensionality using multiple random embeddings, Random projections of linear and semidefinite problems with linear inequalities, Random projections for conic programs

Uses Software

• CPLEX
• Netlib
• Julia

Cites Work

• Unnamed Item
• Unnamed Item
• Understanding and using linear programming
• On the complexity of a pivot step of the revised simplex algorithm
• The simplex method. A probabilistic analysis
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Interior-point methods
• A sparse Johnson
• Quantile Regression for Large-Scale Applications
• Julia: A Fresh Approach to Numerical Computing
• Sparser Johnson-Lindenstrauss Transforms
• Extensions of Lipschitz mappings into a Hilbert space
• Computing in Operations Research Using Julia
• On variants of the Johnson–Lindenstrauss lemma
• Decoding by Linear Programming
• Nearest-neighbor-preserving embeddings
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Sparse Approximate Solutions to Linear Systems
• The Johnson-Lindenstrauss Transform: An Empirical Study
• On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming