Polynomial algorithms for a class of linear programs

1. S. Agmon, “The relaxation method for linear inequalities”,Canadian Journal of Mathematics 6 (1954) 382–392.

   Google Scholar 

2. S.A. Cook, “The complexity of theorem proving procedures”, in:Conf. Rec. of 3^rd ACM Symposium on Theory of Computing (1970) 151–158.

3. G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, NJ, 1963).

   Google Scholar 

4. J. Edmonds, “Paths, trees, and flowers”,Canadian Journal of Mathematics 17 (1965) 449–467.

   Google Scholar 

5. J. Edmonds, “Systems of distinct representatives and linear algebra”,Journal of Research of the National Bureau of Standards — B 71B (1967) 241–245.

   Google Scholar 

6. J. Edmonds and R.M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems”,Journal of the Association for Computing Machinery 19 (1972) 248–264.

   Google Scholar 

7. A.J. Hoffman and J.B. Kruskal, “Integral boundary points of convex polyhedra”, in: H.W. Kuhn and A.W. Tucker, eds.,Linear inequalities and related systems (Princeton University Press, Princeton, NJ, 1956).

   Google Scholar 

8. R.G. Jeroslow, “Some relaxation methods for linear inequalities”,Cahiers du Centre d'Études de Recherche Opérationnelle 21 (1979) 43–53.

   Google Scholar 

9. R.M. Karp, “Reducibility among combinatorial problems”, in: R.E. Miller, et al. eds.,Complexity of computer computations (Plenum Press, New York, 1972).

   Google Scholar 

10. L.G. Khachijan, “A polynomial algorithm in linear programming”,Soviet Mathematics Doklady 20 (1979) 191–194.

    Google Scholar 

11. L. Lovász, “Normal hypergraphs and the perfect graph conjecture”,Discrete Mathematics 2 (1972) 253–267.

    Google Scholar 

12. J.F. Maurras, “Bon algorithmes, vieilles idées”, NoteE.d.F. HR 32.0320, 1978.

13. J.F. Maurras, “Good algorithms, old ideas”, manuscript, 1978.

14. T.S. Motzkin and I.J. Schoenberg, “The relaxation method for linear inequalities”,Canadian Journal of Mathematics 6 (1954) 393–404.

    Google Scholar 

15. P.D. Seymour, “Decomposition of regular matroids”,Journal of Combinatorial Theory(B) 28 (1980) 305–359.

    Google Scholar 

16. N.Z. Shor, “Convergence rate of the gradient descent method with dilatation of the space”,Cybernetics 6 (1970) 102–108.

    Google Scholar 

17. A.F. Veinott, Jr. and G.B. Dantzig, “Integral extreme points”,SIAM Review 10 (1968) 371–372.

    Google Scholar 

Download references