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 (13)

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 linear programming: an improved retrieval phase ⋮ Random projections for conic programs ⋮ Random projections for semidefinite programming

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

This page was built for publication: Random Projections for Linear Programming