Criss-cross algorithm
![The criss-cross algorithm visits all 8 corners of the Klee–Minty cube in the worst case. It visits 3 additional corners on average. The Klee–Minty cube is a perturbation of the cube shown here.](/Images/godic/202501/07/Unitcube.svg4332.png")
![In its second phase, the simplex algorithm crawls along the edges of the polytope until it finally reaches an optimum vertex. The criss-cross algorithm considers bases that are not associated with vertices, so that some iterates can be in the interior of the feasible region, like interior-point algorithms; the criss-cross algorithm can also have infeasible iterates outside the feasible region.](/Images/godic/202501/07/Simplex_description4332.png")
![The worst-case computational complexity of Khachiyan's ellipsoidal algorithm is a polynomial. The criss-cross algorithm has exponential complexity.](/Images/godic/202501/07/Ellipsoid_24333.png")
![](/Images/godic/202501/07/Max-flow_min-cut_example.svg4333.png")
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.