Abstract
Polyhedra related to matroids and sub- or supermodular functions play a central role in combinatorial optimization. The purpose of this paper is to present a unified treatment of the subject. The structure of generalized polymatroids and submodular flow systems is discussed in detail along with their close interrelation. In addition to providing several applications, we summarize many known results within this general framework.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Balas, “A linear characterization of permutation vectors,” Management Science Research Report No. 364, Carnegie-Mellon University, Pittsburgh, PA (1975).
E. Balas and W. Pulleyblank, “The perfectly matchable subgraph polytope of bipartite graphs,”Networks 13 (1983) 495–516.
R.E. Bixby, W.H. Cunningham and D.M. Topkis, “The partial order of a polymatroid extreme point,”Mathematics of Operations Research 10 (1985) 367–378.
O. Boruvka, “O jistém problému minimálnim“ (with extended abstract in German),Acte Societatis Scientiarium Naturalium Moravicae, Tomus III, Fasc. 3, Signature F23 (1926) 37–58.
Cai Mao-Cheng, “Arc-disjoint arborescences of diagraphs,”Journal of Graph Theory 7 (1983) 235–240.
W. Cook, “On box totally dual integral polyhedra,”Mathematical Programming 34 (1986) 48–61.
W.H. Cunningham, “An unbounded matroid intersection polyhedron,”Linear Algebra and its Applications 16 (1977) 209–215.
W.H. Cunningham, “Optimal attack and reinforcement of a network,”Journal of the Association for Computing Machinery 32 (1985) 549–561.
W.H. Cunningham, “On submodular function minimization,”Combinatorica 5 (1985) 185–192.
W.H. Cunningham and A. Frank, “A primal-dual algorithm for submodular flows,”Mathematics of Operations Research 10 (1985) 251–262.
F.D.J. Dunstan, “Matroids and submodular functions,”Quarterly Journal of Mathematics Oxford 27 (1976) 339–347.
J. Edmonds, “Minimum partition of a matroid into independent sets,”Journal of Research of the National Bureau of Standards Section B 69 (1965) 67–72.
J. Edmonds, “Lehman's switching game and a theorem of Tutte and Nash-Williams,”Journal of Research of the National Bureau of Standards Section B 69 (1965) 73–77.
J. Edmonds, “Submodular functions, matroids, and certain polyhedra,” in: R. Guy, H. Hanani, N. Sauer and J. Schonheim, eds.,Combinatorial Structures and their Applications (Gordon and Breach, New York 1970) pp. 69–87.
J. Edmonds, “Matroids and the greedy algorithm,”Mathematical Programming 1 (1971) 127–136.
J. Edmonds, “Edge-disjoint branchings,” in: R. Rustin, ed.,Combinatorial Algorithms (Algorithmic Press, New York, 1973) pp. 91–96.
J. Edmonds, “Matroid intersection,”Annals of Discrete Mathematics 4 (1979) 39–49.
J. Edmonds and R. Giles, “A min-max relation for submodular functions on graphs,”Annals of Discrete Mathematics 1 (1977) 185–204.
J. Fonlupt and A. Zemirline, “On the number of common bases of two matroids,”Discrete Mathematics 45 (1983) 217–228.
L.R. Ford and D.R. Fulkerson,Flows in Networks (Princeton University Press, Princeton, NJ, 1962).
A. Frank, “Kernel systems of directed graphs,”Acta Universities Szegediensis 41 (1979) 63–76.
A. Frank, “On the orientation of graphs,”Journal of Combinatorial Theory B 28 (1980) 251–261.
A. Frank, “How to make a digraph strongly connected,”Combinatorica 1 (1981) 145–153.
A. Frank, “On disjoint trees and arborescences,” in: L. Lovász and V.T. Sós, eds.,Algebraic Methods in Graph Theory (North-Holland, Amsterdam-New York, 1981) pp. 159–170.
A. Frank, “A weighted matroid intersection algorithm,”Journal of Algorithms 2 (1981) 328–336.
A. Frank, “An algorithm for submodular functions on graphs,” in: A. Bachem, M. Grötschel and B. Korte, eds., Bonn Workshop on Combinatorial Optimization, Bonn 1980, North-Holland Mathematics Studies 66 (North-Holland, Amsterdam-New York, 1982) pp. 97–120.
A. Frank, “Finding feasible vectors of Edmonds-Giles polyhedra,”Journal of Combinatorial Theory B 36 (1984) pp. 221–239.
A. Frank, “Submodular flows,” in: W.R. Pulleyblank, ed.,Progress in Combinatorial Optimization (Academic Press, Toronto, Ontario, 1984) pp. 147–166.
A. Frank, “Generalized polymatroids,” in: A. Hajnal et. al., eds.,Finite and Infinite Sets (North-Holland, Amsterdam-New York, 1984) pp. 285–294.
A. Frank and A. Gyárfás, “How to orient the edges of a graph,” in: A. Hajnal and V.T. Sós, eds.,Combinatorics (North-Holland, Amsterdam-New York, 1978) pp. 353–363.
A. Frank and É. Tardos, “Matroids from crossing families,” in: A. Hajnal et. al., eds.,Finite and Infinite Sets (North-Holland, Amsterdam-New York, 1984) pp. 295–304.
A. Frank and É. Tardos, “An algorithm for the unbounded matroid intersection polyhedron,” in: R.E. Burkard, R.A. Cunninghame-Green and U. Zimmermann, eds.,Algebraic and Combinatorial Methods in Operations Research, North-Holland Mathematics Studies 95,Annals of Discrete Mathematics 19 (North-Holland, Amsterdam-New York, 1984) pp. 129–134.
A. Frank and É. Tardos, “An application of submodular flows,” to appear inLinear Algebra and its Applications.
A. Frank, A. Sebö and É. Tardos, “Covering directed and odd cuts,”Mathematical Programming Studies 22 (1984) 99–112.
S. Fujishige, “Algorithms for solving the independent flow problems,”Journal of the Operations Research Society of Japan 21 (1978) 189–203.
S. Fujishige, “Structures of polyhedra determined by submodular functions on crossing families,”Mathematical Programming 29 (1984) 125–141.
S. Fujishige, “A note on Frank's generalized polymatroids,”Discrete Applied Mathematics 7 (1984) 105–109.
S. Fujishige, “A characterization of faces of the base polyhedron associated with a submodular system,”Journal of the Operations Research Society of Japan 27 (1984) 112–128.
S. Fujishige, “Submodular systems and related topics,” in B. Korte and K. Ritter, eds.,Mathematical Programming Study 22 (1984) 113–131.
S. Fujishige and N. Tomizawa, “A note on submodular functions on distributive lattices,”Journal of the Operations Research Society of Japan 26 (1983) 309–318.
D. Gale, “Optimal assignments in an ordered set: An application of matroid theory,”Journal of Combinatorial Theory 4 (1968) 176–190.
R. Giles, “Submodular functions, graphs and integer polyhedra,” Ph.D. Thesis, Department of Combinatorics and Optimization, University of Waterloo, Canada, 1975.
H. Gröflin and A.J. Hoffman, “On matroid intersections,”Combinatorica 1 (1981) 43–47.
H. Gröflin and T.M. Liebling, “Connected and alternating vectors, polyhedra and algorithms,”Mathematical Programming 20 (1981) 233–244.
M. Grötschel, L. Lovász and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–187.
R. Hassin, “Minimum cost flow with set-constraints,”Networks 12 (1982) 1–22.
D.A. Higgs, “Strong maps of geometries,”Journal of Combinatorial Theory 5 (1968) 185–191.
A. Hoffman, “Some recent applications of the theory of linear inequalities to extremal combinatorial analysis,” in:Proceedings of the Symposium of Applied Mathematics 10 (American Mathematical Society, Providence RI, 1960) pp. 113–127.
A. Hoffman, “A generalization of max-flow-min-cut,”Mathematical Programming 6 (1974) 352–359.
A.J. Hoffman, “Ordered sets and linear programming,” in: I. Rival, ed.,Ordered Sets (D. Reidel Publishing Company, Dordrecht-Boston, MA, 1982) pp. 619–654.
T.C. Hu,Integer Programming and Network Flows (Addison-Wesley Publishing Company, Reading MA, 1969) pp. 173–175.
H. Imai, “Network-flow algorithms for lower truncated transversal polymatroids,”Journal of the Operations Research Society of Japan 26 (1983) 186–210.
E.L. Lawler, “Matroid intersection algorithms,”Mathematical Programming 9 (1975) 31–56.
E.L. Lawler and C.U. Martel, “Computing maximal “polymatroidal” network flows,”Mathematics of Operations Research (1982) 334–347.
L. Lovász, “A generalization of König's theorem,”Acta Mathematica Academiae Scientiarum Hungaricae 21 (1970) 443–446.
L. Lovász, “Flats in matroids and geometric graphs“ in: P.J. Cameron, ed.,Combinatorial Surveys, Proceedings of the 6th British Combinatorial Conference (Academic Press, London, 1977) pp. 45–86.
L. Lovász, “Submodular functions and convexity,” in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programming: The State of the Art (Springer-Verlag, Berlin-New York, 1983) pp. 235–257.
L. Lovász and Y. Yemini, “On generic rigidity in the plane,”SIAM Journal on Algebraic and Discrete Methods 3 (1982) 91–98.
C.L. Lucchesi and D.H. Younger, “A minimax relation for directed graphs,”Journal of the London Mathematical Society Second Series (1978) 369–374.
C. Mao-Cheng, “Arc-disjoint arborescences of digraphs,”Journal of Graph Theory 7 (1973) 235–240.
C.J.H. McDiarmid, “Independence structures and submodular functions,”Bulletin of the London Mathematical Society 29 (1973) 18–20.
C.J.H. McDiarmid, “Rado's theorem for polymatroids,”Mathematical Proceedings of the Cambridge Philosophical Society 78 (1975) 263–281.
C.J.H. McDiarmid, “Blocking, anti-blocking, and pairs of matroids and polymatroids,”Journal of Combinatorial Theory B 25 (1978) 313–325.
C.St.J.A. Nash-Williams, “An application of matroids to graph theory,” in: P. Rosenstiehl, ed.,Theory of Graphs (Proceedings International Symposium Roma, 1966) (Gordon and Breach, New York and Dunod, Paris, 1967) pp. 263–265.
C.St.J.A. Nash-Williams, “Well-balanced orientation of finite graphs and unobtrusive odd-vertex pairing,” in: W.T. Tutte, ed.,Recent Progress in Combinatorics (Academic Press, New York, 1969) pp. 133–149.
W.R. Pulleyblank, “Polyhedral combinatorics,” in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programming: The State of the Art (Springer-Verlag, 1983) pp. 312–345.
R. Rado, “A theorem on independence functions,”Quarterly Journal of Mathematics, Oxford 13 (1942) 83–89.
R. Rado, “Note on independence functions,”Proceedings of the London Mathematical Society, Third Series 7 (1957) 300–320.
L.S. Shapley, “Cores of convex games,”International Journal of Game Theory 1 (1971) 11–26.
P. Schönsleben, “Ganzzahlige Polymatroid-Intersektions-Algorithmen,” Ph.D. Thesis, Eidgenössischen Technischen Hochschule, Zürich, 1980.
A. Schrijver, “On total dual integrality,”Linear Algebra and its Applications 38 (1981) 27–32.
A. Schrijver, “Packing and covering of crossing families of cuts,”Journal of Combinatorial Theory B 35 (1983) 104–128.
A. Schrijver, “Total dual integrality from directed graphs, crossing families and sub- and supermodular functions,” in: W.R. Pulleyblank, ed.,Progress in Combinatorial Optimization (Academic Press, Toronto, Ontario, 1984) pp. 315–362.
A. Schrijver, “Proving total dual integrality with cross-free families—a general framework,”Mathematical Programming 29 (1984) 15–27.
A. Schrijver, “Supermodular colourings,” in: A. Recski, L. Lovász, eds.,Matroid Theory, Colloquia Mathematica Societatis János Bolyai 40 (North-Holland, Amsterdam-New York, 1985) pp. 327–344.
A. Schrijver,Theory of Linear and Integer Programming (Wiley, New York, 1986).
É. Tardos, “Generalized matroids and supermodular colourings,” in: A. Recski and L. Lovász, eds.,Matroid Theory, Colloquia Mathematica Societatis János Bolyai 40 (North-Holland, Amsterdam-New York, 1985) pp. 359–382.
É. Tardos, C.A. Tovey and M.A. Trick, “Layered augmenting path algorithms,”Mathematics of Operations Research 11 (1986) 362–370.
D.M. Topkis, “Adjacency on polymatroids,”Mathematical Programming 30 (1984) 229–237.
W.T. Tutte, “On the problem of decomposing a graph inton connected factors,”Journal of the London Mathematical Society 36 (1961) 221–230.
K. Vidyasankar, “Covering the edge set of a directed graph with trees,”Discrete Mathematics 24 (1978) 79–85.
K. Vidyasankar and D. Younger, “A minimax equality related to the longest directed path in an acyclic graph,”Canadian Journal of Mathematics 27 (1975) 348–351.
V.A. Yemelichev, M.M. Kovalev and M.K. Kravtscv,Polytopes, Graphs and Optimization (Cambridge University Press, Cambridge, UK, 1984).
D.J.A. Welsh, “Kruskal's theorem for matroids,”Proceedings of the Cambridge Philosophical Society 64 (1968) 3–4.
D.J.A. Welsh,Matroid Theory (Academic Press, London, 1976).
U. Zimmermann, “Minimization on submodular flows,”Discrete Applied Mathematics 4 (1982) 303–323.
Author information
Authors and Affiliations
Additional information
Supported by a grant from the Alexander von Humboldt Stiftung and by the Institut für Ökonometrie und Operations Research of the University of Bonn, Bonn, Nassestr. 2, Federal Republic of Germany.
Rights and permissions
About this article
Cite this article
Frank, A., Tardos, É. Generalized polymatroids and submodular flows. Mathematical Programming 42, 489–563 (1988). https://doi.org/10.1007/BF01589418
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01589418