Criss-cross methods: A fresh view on pivot algorithms

DOI10.1007/BF02614325zbMATHDBLPOpenAlexWikidataMaRDI QIDQ1365063FDO

Authors Komei Fukuda, Tamás Terlaky

Publication date 1 June 1998

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

cyclingrecursionoriented matroidscriss-cross methodpivot rules

Mathematics Subject Classification ID

Quadratic programming (90C20) Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Recommendations

• New variants of finite criss-cross pivot algorithms for linear programming
• scientific article; zbMATH DE number 1226265
• The criss-cross method can take \(\Omega(n^d)\) pivots
• scientific article; zbMATH DE number 5011461
• Analysis of the Diagonal Pivoting Method
• Comparing pivoting strategies for almost strictly sign regular matrices
• Pivot vector method and its applications
• The Criss-Cross Method for Solving Linear Programming Problems
• The principal pivoting method revisited

Cites work

• scientific article; zbMATH DE number 4199652 (Why is no real title available?)
• scientific article; zbMATH DE number 14316 (Why is no real title available?)
• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3523317 (Why is no real title available?)
• scientific article; zbMATH DE number 3626518 (Why is no real title available?)
• scientific article; zbMATH DE number 1021641 (Why is no real title available?)
• scientific article; zbMATH DE number 819135 (Why is no real title available?)
• scientific article; zbMATH DE number 3332061 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• A Note on Convergence of the Ford-Fulkerson Flow Algorithm
• A combinatorial abstraction of linear programming
• A convergent criss-cross method
• A finite crisscross method for oriented matroids
• A general deterministic pivot method for oriented matroid programming
• A new polynomial-time algorithm for linear programming
• A new proof for the criss-cross method for quadratic programming
• A note on the Edmonds-Fukuda pivoting rule for simplex algorithms
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• An exponential example for Terlaky's pivoting rule for the criss-cross simplex method
• Complementarity in Oriented Matroids
• Complementary pivot theory of mathematical programming
• Computational complexity of parametric linear programming
• EP theorems and linear complementarity problems
• Equilibrium Points of Bimatrix Games
• Finding all common bases in two matroids
• Interior point methods of mathematical programming
• LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS
• Linear quadratic programming in oriented matroids
• New Finite Pivoting Rules for the Simplex Method
• On anti-cycling pivoting rules for the simplex method
• On extremal behaviors of Murty's least index method
• On the finiteness of the criss-cross method
• Optimality and Degeneracy in Linear Programming
• Orientability of matroids
• Pivot rules for linear programming: A survey on recent theoretical developments
• Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• Some Empirical Tests of the Criss-Cross Method
• Some generalizations of the criss-cross method for quadratic programming
• Some generalizations of the criss-cross method for the linear complementarity problem of oriented matroids
• Sufficient matrices and the linear complementarity problem
• Symmetric dual quadratic programs
• Symmetry and positive definiteness in oriented matroids
• The d-Step Conjecture and Its Relatives
• The Criss-Cross Method for Solving Linear Programming Problems
• The Existence of a Short Sequence of Admissible Pivots to an Optimal Basis in LP and LCP
• The finite criss-cross method for hyperbolic programming
• The generalized simplex method for minimizing a linear form under linear inequality restraints
• The linear complementarity problem, sufficient matrices, and the criss- cross method
• The simplex algorithm with a new primal and dual pivot rule
• The simplex method. A probabilistic analysis
• What is the worst case behavior of the simplex algorithm?
• \(P_ *\)-matrices are just sufficient

Cited in

(24)

• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Predictor-corrector interior-point algorithm for \(P_*(\kappa)\)-linear complementarity problems based on a new type of algebraic equivalent transformation technique
• A phase-1 approach for the generalized simplex algorithm
• Diameters of cocircuit graphs of oriented matroids: an update
• Pivot versus interior point methods: Pros and cons
• Exterior point simplex-type algorithms for linear and network optimization problems
• Combinatorial redundancy detection
• A primal deficient-basis simplex algorithm for linear programming
• scientific article; zbMATH DE number 1226265 (Why is no real title available?)
• Interior-point algorithm for sufficient LCPs based on the technique of algebraically equivalent transformation
• New variants of the criss-cross method for linearly constrained convex quadratic programming
• New variants of finite criss-cross pivot algorithms for linear programming
• On the existence of a short pivoting sequence for a linear program
• Feasible corrector-predictor interior-point algorithm for \(P_* (\kappa)\)-linear complementarity problems based on a new search direction
• The sagitta method for solving linear programs
• A convergent criss-cross method
• The criss-cross method can take \(\Omega(n^d)\) pivots
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Tropicalizing the simplex algorithm
• The finite criss-cross method for hyperbolic programming
• A simplex based algorithm to solve separated continuous linear programs
• Circuit walks in integral polyhedra
• Edges versus circuits: a hierarchy of diameters in polyhedra
• Exact methods for large-scale multi-period financial planning problems

This page was built for publication: Criss-cross methods: A fresh view on pivot algorithms

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