scientific article; zbMATH DE number 3626518

zbMath0403.65025MaRDI QIDQ4188659

Vašek Chvátal, David Avis

Publication date: 1978

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Monte Carlo ExperimentsSimplex MethodPivotingPivot Selection400 Iterations on the AverageDegeneracy and CyclingKlee-Minty ExamplesNumber of IterationsRandomly Generated Problems

Mathematics Subject Classification ID

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

Related Items (32)

Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday) ⋮ The Klee–Minty random edge chain moves with linear speed ⋮ A note on the Edmonds-Fukuda pivoting rule for simplex algorithms ⋮ A multiplicative barrier function method for linear programming ⋮ Survey of solved and open problems in the degeneracy phenomenon ⋮ Affirmative action algorithms ⋮ A dual approach to primal degeneracy ⋮ Criss-cross methods: A fresh view on pivot algorithms ⋮ Computational behavior of a feasible direction method for linear programming ⋮ Reverse search for enumeration ⋮ Worst case behavior of the steepest edge simplex method ⋮ An exponential lower bound for Zadeh's pivot rule ⋮ An exponential example for Terlaky's pivoting rule for the criss-cross simplex method ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ A double-pivot simplex algorithm and its upper bounds of the iteration numbers ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ On anti-cycling pivoting rules for the simplex method ⋮ A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games ⋮ A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra ⋮ A computational study of redundancy in randomly generated polytopes ⋮ On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes ⋮ An efficient simplex type algorithm for sparse and dense linear programs. ⋮ The ellipsoid method and its implications ⋮ Randomly generated polytopes for testing mathematical programming algorithms ⋮ Selected bibliography on degeneracy ⋮ Degeneracy graphs: Theory and applications. An updated survey ⋮ Pivot rules for linear programming: A survey on recent theoretical developments ⋮ An exterior point simplex algorithm for (general) linear programming problems ⋮ An interior feasible direction method with constraint projections for linear programming ⋮ The Average number of pivot steps required by the Simplex-Method is polynomial ⋮ Random polytopes: Their definition, generation and aggregate properties ⋮ Estimating the number of vertices of a polyhedron

This page was built for publication: