×

zbMATH — the first resource for mathematics

On the non-polynomiality of the relaxation method for systems of linear inequalities. (English) Zbl 0473.90051

MSC:
90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Agmon, ”The relaxation method for linear inequalities,Canadian Journal of Mathematics 6 (1954) 382–392. · Zbl 0055.35001 · doi:10.4153/CJM-1954-037-2
[2] P. Gacs and L. Lovasz, ”Khacian’s algorithm for linear programming”, Report C.S. 750, Computer Science Department, Stanford University (Stanford, CA, 1979).
[3] J.L. Goffin, ”The relaxation method for solving systems of linear inequalities”,Mathematics of Operation Research 5 (1980) 388–414. · Zbl 0442.90051 · doi:10.1287/moor.5.3.388
[4] J.L. Goffin, ”Acceleration in the relaxation method for linear inequalities and subgradient optimization”, working paper 79-10; Faculty of Management, McGill University, April 1979, to appear in the proceedings of a task force on nondifferentiable optimization held at IIASA, Laxenburg, Austria, December 1978.
[5] L.G. Khacian, ”A polynomial algorithm for linear programming”,Doklady Akademii Nauk SSSR, 244 (5) (1979) 1093–1095, translated inSoviet Mathematics Doklady 20 (1) (1979) 191–194.
[6] T. Motzkin and I.Y. Schoenberg, ”The relaxation method for linear inequalities”,Canadian Journal of Mathematics 6 (1954) 393–404. · Zbl 0055.35002 · doi:10.4153/CJM-1954-038-x
[7] A.M. Ostrowski, ”On over and under relaxation in the theory of the cyclic single step iteration”,Mathematical Tables and other Aids to Computation 7 (1953) 152–159. · Zbl 0053.26201 · doi:10.2307/2002755
[8] C.J. Papadimitriou, ”Efficient search for rationals”,Information Processing Letters 8 (1979) 1–4. · Zbl 0411.65037 · doi:10.1016/0020-0190(79)90079-6
[9] N.Z. Shor, ”Convergence rate of the gradient descent method with dilatation of the space”,Kibernetika 6 (2) (1970) 80–85, translated inCybernetics 6 (2) (1970) 102–108. · Zbl 0243.90038
[10] N.Z. Shor, ”Cut-off method with space extension on convex programming problems”,Kibernetika 13 (6) (1977) 94–95, translated inCybernetics 13 (6) (1977) 94–96.
[11] V.A. Skokov, ”Note on minimization methods using space dilatation”,Kibernetika 10 (4) (1974) 115–117, translated inCybernetics 10 (4) (1974) 689–692.
[12] D.B. Yudin and A.S. Nemirovskii, ”Informational complexity and effective methods for the solution of convex extremal problems”,Ekonomika I Mathematicheskie Metody 12 (2) (1976) 357–369, translated inMatekon 13 (3) (1977) 25–45. · Zbl 0329.90054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.