×

The ellipsoid method and its consequences in combinatorial optimization. (English) Zbl 0492.90056


MSC:

90C10 Integer programming
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
90C05 Linear programming
90C09 Boolean programming
Full Text: DOI

References:

[1] Chu Yoeng-jin andLiu Tseng-hung, On the shortest arborescence of a directed graph,Scientia Sinica 4 (1965) 1396–1400. · Zbl 0178.27401
[2] E. W. Dijkstra, A note on two problems in connexion with graphs,Numer. Math. 1 (1959) 269–271. · Zbl 0092.16002 · doi:10.1007/BF01386390
[3] J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices,J. Res. Nat. Bur. Standards Sect. B 69 (1965) 125–130. · Zbl 0141.21802
[4] J. Edmonds, Optimum branchings,J. Res. Nat. Bur. Standards Sect. B 71 (1967) 233–240. · Zbl 0155.51204
[5] J. Edmonds, Submodular functions, matroids, and certain polyhedra, in:Combinatorial structures and their applications, Proc. Intern. Conf. Calgary, Alb., 1969 (R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds.), Gordon and Breach, New York, 1970, 69–87.
[6] J. Edmonds andE. L. Johnson, Matching: a well-solved class of integer linear programs, –ibid. 89–92. · Zbl 0258.90032
[7] J. Edmonds, Edge-disjoint branchings, in:Combinatorial algorithms, Courant Comp. Sci. Symp. Monterey, Ca., 1972 (R. Rustin, ed.), Acad. Press, New York, 1973, 91–96.
[8] J. Edmonds, Matroid intersection,Annals of Discrete Math. 4 (1979) 39–49. · Zbl 0416.05025 · doi:10.1016/S0167-5060(08)70817-3
[9] J. Edmonds andR. Giles, A min-max relation for submodular functions on graphs,Annals of Discrete Math. 1 (1977) 185–204. · Zbl 0373.05040 · doi:10.1016/S0167-5060(08)70734-9
[10] J. Edmonds andE. L. Johnson, Matching, Euler tours and the Chinese postman,Math. Programming 5 (1973) 88–124. · Zbl 0281.90073 · doi:10.1007/BF01580113
[11] L. R. Ford andD. R. Fulkerson, Maximum flow through a network,Canad. J. Math. 8 (1956) 399–404. · Zbl 0073.40203 · doi:10.4153/CJM-1956-045-5
[12] L. R. Ford andD. R. Fulkerson,Flows in networks, Princeton Univ. Press, Princeton, N. J., 1962. · Zbl 0106.34802
[13] A. Frank, On the orientations of graphs,J. Combinatorial Theory (B) 28 (1980) 251–260. · Zbl 0443.05045 · doi:10.1016/0095-8956(80)90071-4
[14] A. Frank, Kernel systems of directed graphs,Acta Sci. Math. (Szeged)41 (1979) 63–76. · Zbl 0425.05028
[15] A. Frank, How to make a digraph strongly connected,Combinatorica 1 (2) (1981) 145–153. · Zbl 0487.05033 · doi:10.1007/BF02579270
[16] D. R. Fulkerson, Networks, frames, and blocking systems, in:Mathematics of the decision sciences, Part I (G. B. Dantzig and A. F. Veinott, eds.), Amer. Math. Soc., Providence, R. I., 1968, 303–334. · Zbl 0182.53402
[17] D. R. Fulkerson, Blocking polyhedra, in:Graph theory and its applications, Proc. adv. Seminar Madison, Wis., 1969 (B. Harris, ed.), Acad. Press, New York, 1970, 93–112.
[18] D. R. Fulkerson, Packing rooted directed cuts in a weighted directed graph,Math. Programming 6 (1974) 1–13. · Zbl 0283.05104 · doi:10.1007/BF01580218
[19] P. Gács andL. Lovász, Khachiyan’s algorithm for linear programming,Math. Programming Studies 14 (1981) 61–68. · Zbl 0463.90066
[20] M. R. Garey andD. S. Johnson,Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979. · Zbl 0411.68039
[21] A. J. Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, in:Combinatorial analysis, Proc. 10th Symp. on Appl. Math. Columbia Univ., 1958 (R. E. Bellman and M. Hall, Jr, eds.), Amer. Math. Soc., Providence, R. I., 1960, 113–127.
[22] I. Holyer, The NP-completeness of edge-colouring,SIAM J. Comp., to appear. · Zbl 0473.68034
[23] T. C. Hu, Multicommodity network flows,Operations Res. 11 (1963) 344–360. · Zbl 0123.23704 · doi:10.1287/opre.11.3.344
[24] T. C. Hu, Two-commodity cut-packing problem,Discrete Math. 4 (1973) 108–109. · Zbl 0255.90067
[25] A. V. Karzanov, On the minimal number of arcs of a digraph meeting all its directed cutsets,to appear.
[26] L. G. Khachiyan, A polynomial algorithm in linear programming,Doklady Akademii Nauk SSSR 244 (1979) 1093–1096 (English translation:Soviet Math. Dokl. 20, 191–194). · Zbl 0414.90086
[27] E. L. Lawler, Optimal matroid intersections, in:Combinatorial structures and their applications, Proc. Intern. Conf. Calgary, Alb., 1969 (R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds.), Gordon and Breach, New York, 1970, 233–235.
[28] E. L. Lawler,Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, New York, 1976. · Zbl 0413.90040
[29] L. Lovász, Normal hypergraphs and the perfect graph conjecture,Discrete Math. 2 (1972) 253–267. · Zbl 0239.05111 · doi:10.1016/0012-365X(72)90006-4
[30] L. Lovász, 2-Matchings and 2-covers of hypergraphs,Acta Math. Acad. Sci. Hungar. 26 (1975) 433–444. · Zbl 0339.05123 · doi:10.1007/BF01902352
[31] L. Lovász, The matroid matching problem,Proc. Conf. Algebraic Methods in Graph Theory (Szeged, 1978), to appear. · Zbl 0478.05027
[32] L. Lovász, On the Shannon capacity of a graph,IEEE Trans. on Information Theory 25 (1979) 1–7. · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985
[33] L. Lovász, Perfect graphs, in:More selected topics in graph theory (L. W. Beineke and R. J. Wilson, eds), to appear
[34] C. L. Lucchesi, A minimax equality for directed graphs,Doctoral Thesis, Univ. Waterloo, Waterloo, Ont., 1976.
[35] C. L. Lucchesi andD. H. Younger, A minimax relation for directed graphs,J. London Math. Soc. (2) 17 (1978) 369–374. · Zbl 0392.05029 · doi:10.1112/jlms/s2-17.3.369
[36] G. J. Minty, On maximal independent sets of vertices in claw-free graphs,J. Combinatorial Theory (B),28 (1980) 284–304. · Zbl 0434.05043 · doi:10.1016/0095-8956(80)90074-X
[37] T. S. Motzkin andI. J. Schoenberg, The relaxation method for linear inequalities,Canad. J. Math. 6 (1954) 393–404. · Zbl 0055.35002 · doi:10.4153/CJM-1954-038-x
[38] H. Okamura andP. D. Seymour, Multicommodity flows in planar graphs,J. Combinatorial Theory (B), to appear. · Zbl 0465.90029
[39] M. W. Padberg andM. R. Rao, Minimum cut-sets and b-matchings,to appear. · Zbl 0499.90056
[40] A. Schrijver, A counterexample to a conjecture of Edmonds and Giles,Discrete Math. 32 (1980) 213–214.
[41] P. D. Seymour, The matroids with the max-flow min-cut property,J. Combinatorial Theory (B) 23 (1977) 189–222. · Zbl 0375.05022 · doi:10.1016/0095-8956(77)90031-4
[42] P. D. Seymour, A two-commodity cut theorem,Discrete Math. 23 (1978) 177–181. · Zbl 0387.05022 · doi:10.1016/0012-365X(78)90116-4
[43] N. Z. Shor, Convergence rate of the gradient descent method with dilatation of the space,Kibernetika 2 (1970) 80–85 (English translation:Cybernetics 6 (1970) 102–108). · Zbl 0243.90038
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.