Abstract
We study the concept of series and parallel composition of linear programming problems and show that greedy properties are inherited by such compositions. Our results are inspired by earlier work on compositions of flow problems. We make use of certain Monge properties as well as convexity properties which support the greedy method in other contexts.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Y.P. Aneja, R. Chandrasekaran and K.P.K. Nair, “Classes of linear programs with integral optimal solutions,”Mathematical Programming Study 25 (1985) 225–237.
W.W. Bein, “Netflows, polymatroids, and greedy structures,” Ph.D. Thesis, Universität Osnabrück (Osnabrück, Germany, 1986).
W.W. Bein and P. Brucker, “Greedy concepts for network flow problems,”Discrete Applied Mathematics 15 (1986) 135–144.
W.W. Bein, P. Brucker and A. Tamir, “Minimum cost flow algorithms for series parallel networks,”Discrete Applied Mathematics 10 (1985) 117–124.
P.C. Gilmore, E.L. Lawler and D.B. Shmoys, “Well-solved special cases,” in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Travelling Salesman Problem — A Guided Tour of Combinatorial Optimization (Wiley, New York, 1985) pp. 87–143.
G.H. Hardy, J.E. Littlewood and G. Polya,Inequalities (Cambridge University Press, Cambridge, England, 1934).
A.J. Hoffman, “On simple linear programming problems,” in: V.L. Klee, ed.,Convexity, Proceedings of Symposia in Pure Mathematics, Vol. 7 (American Mathematical Society, Providence, RI, 1963) pp. 317–327.
A.J. Hoffman, “On greedy algorithms that succeed,” in: I. Anderson, ed.,Surveys in Combinatorics 1985. London Mathematical Society Lecture Note Series No. 103 (Cambridge University Press, Cambridge, England, 1985) pp. 97–112.
A.J. Hoffman, “On greedy algorithms for series parallel graphs,”Mathematical Programming 40 (1988) 197–204.
J. Kahn, oral communication (1988).
G. Monge, “Mémoire sur la théorie des déblai et des remblai,”Histoire de l'Academie Royale des Sciences (année 1781) (Paris, 1784) pp. 666–704.
C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization (Prentice-Hall, Englewood Cliffs, NJ, 1982).
J. Valdes, “Parsing flowcharts and series-parallel graphs,” Ph.D. Thesis, Stanford University (Stanford, CA, 1978).
Author information
Authors and Affiliations
Additional information
This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.
Rights and permissions
About this article
Cite this article
Bein, W.W., Brucker, P. & Hoffman, A.J. Series parallel composition of greedy linear programming problems. Mathematical Programming 62, 1–14 (1993). https://doi.org/10.1007/BF01585157
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585157