Criss-cross algorithm
In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems.
- Abstraction100002137
- Act100030358
- Activity100407535
- Algorithm105847438
- Event100029378
- Procedure101023820
- PsychologicalFeature100023100
- Rule105846932
- Thing
- WikicatCombinatorialAlgorithms
- WikicatExchangeAlgorithms
- WikicatGeometricAlgorithms
- WikicatOptimizationAlgorithmsAndMethods
- YagoPermanentlyLocatedEntity
- Comment
- enIn mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems.
- Depiction
- Has abstract
- enIn mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems. Like the simplex algorithm of George B. Dantzig, the criss-cross algorithm is not a polynomial-time algorithm for linear programming. Both algorithms visit all 2D corners of a (perturbed) cube in dimension D, the Klee–Minty cube (after Victor Klee and George J. Minty), in the worst case. However, when it is started at a random corner, the criss-cross algorithm on average visits only D additional corners. Thus, for the three-dimensional cube, the algorithm visits all 8 corners in the worst case and exactly 3 additional corners on average.
- Is primary topic of
- Criss-cross algorithm
- Label
- enCriss-cross algorithm
- Link from a Wikipage to an external page
- core.ac.uk/download/pdf/6714737.pdf%7Cdoi=10.1016/0024-3795(93)90124-7%7Cmr=1221693%7Cdoi-access=free
- www.cs.elte.hu/opres/orr/download/ORR03_1.pdf%7Cformat=pdf%3C!--%7Ceprint=http:/www.tandfonline.com/doi/pdf/10.1080/10556780500095009--%3E
- www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a
- www.cas.mcmaster.ca/~terlaky/files/crisscross.ps
- www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz
- coral.ie.lehigh.edu/~terlaky/
- web.archive.org/web/20110728105602/http:/www.ifor.math.ethz.ch/~fukuda/
- web.archive.org/web/20110728105643/http:/www.ifor.math.ethz.ch/~fukuda/publ/publ.html
- coral.ie.lehigh.edu/~terlaky/publications
- Link from a Wikipage to another Wikipage
- Algorithm
- Arithmetic operation
- Average case complexity
- Average-case complexity
- Big oh
- Big Oh notation
- Bland's rule
- Buchberger's algorithm
- Category:Combinatorial algorithms
- Category:Combinatorial optimization
- Category:Exchange algorithms
- Category:Geometric algorithms
- Category:Linear programming
- Category:Optimization algorithms and methods
- Category:Oriented matroids
- Combinatorics
- Convex hull
- Cubic polynomial
- David Avis
- Degree of a polynomial
- Dimension (vector space)
- Discrete and Computational Geometry
- Ellipsoidal algorithm
- Facet
- Farkas lemma
- File:Ellipsoid 2.png
- File:Max-flow min-cut example.svg
- File:Simplex description.png
- File:Unitcube.svg
- Gaussian elimination
- George Dantzig
- George J. Minty
- Interior-point method
- Jack Edmonds
- Karmarkar
- Karmarkar's algorithm
- Khachiyan
- Klee–Minty cube
- Komei Fukuda
- Linear algebra
- Linear complementarity problem
- Linear-fractional programming
- Linear inequality
- Linear programming
- Linear system
- Michael J. Todd (mathematician)
- Multivariate polynomial
- Nonlinear programming
- Optimization (mathematics)
- Oriented matroid
- P-matrix
- Polyhedron
- Positive-definite matrix
- Principal minor
- Quadratic programming
- Real number
- Sign function
- Simplex algorithm
- Space complexity
- Sufficient matrix
- Tamas Terlaky
- Time complexity
- Unit cube
- Vertex enumeration problem
- Victor Klee
- Worst case complexity
- Worst-case complexity
- SameAs
- Criss-cross algorithm
- ftTy
- m.0gj964k
- Q17006040
- ক্রিস-ক্রস এ্যালগোরিদম
- SeeAlso
- Linear programming
- Subject
- Category:Combinatorial algorithms
- Category:Combinatorial optimization
- Category:Exchange algorithms
- Category:Geometric algorithms
- Category:Linear programming
- Category:Optimization algorithms and methods
- Category:Oriented matroids
- Thumbnail
- WasDerivedFrom
- Criss-cross algorithm?oldid=1094666421&ns=0
- WikiPageLength
- 24298
- Wikipage page ID
- 31255067
- Wikipage revision ID
- 1094666421
- WikiPageUsesTemplate
- Template:!
- Template:About
- Template:Cite journal
- Template:Expand section
- Template:Mathematical programming
- Template:Optimization algorithms
- Template:See also
- Template:Short description
- Template:Use dmy dates
