The ellipsoid method and its consequences in combinatorial optimization

M. Grötschel; L. Lovász; A. Schrijver

doi:10.1007/bf02579273

journal article Jun 01, 1981

The ellipsoid method and its consequences in combinatorial optimization

M. Grötschel L. Lovász A. Schrijver

Combinatorica Vol. 1 No. 2 pp. 169-197 · Springer Science and Business Media LLC

View at Publisher Save 10.1007/bf02579273

Topics

No keywords indexed for this article. Browse by subject →

References

43

[1]

Chu Yoeng-jin andLiu Tseng-hung, On the shortest arborescence of a directed graph,Scientia Sinica 4 (1965) 1396–1400.

[2]

A note on two problems in connexion with graphs

E. W. Dijkstra

Numerische Mathematik 1959 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. 10.6028/jres.069b.013

[4]

J. Edmonds, Optimum branchings,J. Res. Nat. Bur. Standards Sect. B 71 (1967) 233–240. 10.6028/jres.071b.032

[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.

[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. 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. 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. 10.1007/bf01580113

[11]

L. R. Ford andD. R. Fulkerson, Maximum flow through a network,Canad. J. Math. 8 (1956) 399–404. 10.4153/cjm-1956-045-5

[12]

L. R. Ford andD. R. Fulkerson,Flows in networks, Princeton Univ. Press, Princeton, N. J., 1962.

[13]

A. Frank, On the orientations of graphs,J. Combinatorial Theory (B) 28 (1980) 251–260. 10.1016/0095-8956(80)90071-4

[14]

A. Frank, Kernel systems of directed graphs,Acta Sci. Math. (Szeged)41 (1979) 63–76.

[15]

A. Frank, How to make a digraph strongly connected,Combinatorica 1 (2) (1981) 145–153. 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.

[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. 10.1007/bf01580218

[19]

P. Gács andL. Lovász, Khachiyan’s algorithm for linear programming,Math. Programming Studies 14 (1981) 61–68. 10.1007/bfb0120921

[20]

M. R. Garey andD. S. Johnson,Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979.

[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. 10.1090/psapm/010/0114759

[22]

I. Holyer, The NP-completeness of edge-colouring,SIAM J. Comp., to appear.

[23]

T. C. Hu, Multicommodity network flows,Operations Res. 11 (1963) 344–360. 10.1287/opre.11.3.344

[24]

T. C. Hu, Two-commodity cut-packing problem,Discrete Math. 4 (1973) 108–109.

[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).

[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.

[29]

L. Lovász, Normal hypergraphs and the perfect graph conjecture,Discrete Math. 2 (1972) 253–267. 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. 10.1007/bf01902352

[31]

L. Lovász, The matroid matching problem,Proc. Conf. Algebraic Methods in Graph Theory (Szeged, 1978), to appear.

[32]

L. Lovász, On the Shannon capacity of a graph,IEEE Trans. on Information Theory 25 (1979) 1–7. 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. 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. 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. 10.4153/cjm-1954-038-x

[38]

H. Okamura andP. D. Seymour, Multicommodity flows in planar graphs,J. Combinatorial Theory (B), to appear.

[39]

M. W. Padberg andM. R. Rao, Minimum cut-sets and b-matchings,to appear.

[40]

A. Schrijver, A counterexample to a conjecture of Edmonds and Giles,Discrete Math. 32 (1980) 213–214. 10.1016/0012-365x(80)90057-6

[41]

P. D. Seymour, The matroids with the max-flow min-cut property,J. Combinatorial Theory (B) 23 (1977) 189–222. 10.1016/0095-8956(77)90031-4

[42]

P. D. Seymour, A two-commodity cut theorem,Discrete Math. 23 (1978) 177–181. 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).

Cited By

1,290

Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring

Édouard Bonnet, Colin Geniet · 2024

SIAM Journal on Computing

Hard to solve instances of the Euclidean Traveling Salesman Problem

Stefan Hougardy, Xianghui Zhong · 2020

Mathematical Programming Computatio...

Semialgebraic Proofs and Efficient Algorithm Design

Noah Fleming, Pravesh Kothari · 2019

Foundations and Trends® in Theoreti...

Optimized Bonferroni approximations of distributionally robust joint chance constraints

Weijun Xie, Shabbir Ahmed · 2019

Mathematical Programming

Costly circuits, submodular schedules and approximate Carathéodory Theorems

Shaileshh Bojja Venkatakrishnan, Mohammad Alizadeh · 2017

Queueing Systems

Data-driven robust optimization

Dimitris Bertsimas, Vishal Gupta · 2017

Mathematical Programming

Graph-Theoretic Approach to Quantum Correlations

Adan Cabello, Simone Severini · 2014

Physical Review Letters

Bayesian Mechanism Design

Jason D. Hartline · 2013

Foundations and Trends® in Theoreti...

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Michel X. Goemans, David P. Williamson · 1995

Journal of the ACM

The Complexity of Multiterminal Cuts

E. Dahlhaus, D. S. Johnson · 1994

SIAM Journal on Computing

A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems

Manfred Padberg, Giovanni Rinaldi · 1991

SIAM Review

Metrics

1,290

Citations

43

References

Details

Published: Jun 01, 1981
Vol/Issue: 1(2)
Pages: 169-197
License: View

Authors

Cite This Article

M. Grötschel, L. Lovász, A. Schrijver (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2), 169-197. https://doi.org/10.1007/bf02579273

The ellipsoid method and its consequences in combinatorial optimization

You May Also Like