Random linear programs with many variables and few constraints

DOI10.1007/BF01582163MaRDI QIDQ3710288zbMATH OpenFDO

Authors

Publication date 1986

Published in Mathematical Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01582163

zbMATH Keywords

average-case analysisrandom linear programsexpected number of pivotsnew versions of the simplex algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Recommendations

• On linear programs with random costs
• Randomized solutions to convex programs with multiple chance constraints
• A Linear Approximation for Chance-Constrained Programming
• Random convex programs
• Randomized methods for linear constraints: convergence rates and conditioning
• scientific article; zbMATH DE number 176291
• Random projections for linear programming
• A randomized algorithm for fixed-dimensional linear programming
• Linear programming — Randomization and abstract frameworks
• A linear programming approach for linear programs with probabilistic constraints

Cites work

• scientific article; zbMATH DE number 3880432 (Why is no real title available?)
• Linear Programming in Linear Time When the Dimension Is Fixed
• On Finding the Maxima of a Set of Vectors
• On the Average Number of Maxima in a Set of Vectors and Applications
• On the average number of steps of the simplex method of linear programming
• Random polytopes: Their definition, generation and aggregate properties
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• The Number of Outcomes in the Pareto-Optimal Set of Discrete Bargaining Games

Cited in

(9)

• The expected number of extreme points of a random linear program
• Random Procedures for Nonredundant Constraint Identification in Stochastic Linear Programs
• scientific article; zbMATH DE number 1870008 (Why is no real title available?)
• Linear programming — Randomization and abstract frameworks
• scientific article; zbMATH DE number 176291 (Why is no real title available?)
• Perturbation analysis of linear programming problems with random parameters
• Random inequality constraint systems with few variables
• On the average condition of random linear programs
• A simplex variant solving an m d linear program in O(min(m 2,d 2)) expected number of pivot steps

This page was built for publication: Random linear programs with many variables and few constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3710288)