Abstract
This paper was written at the Rensselaer Polytechnic Institute in 1963. A lecture based on it was given at the Rand Corporation in 1965 and this version is in the form in which Ray Fulkerson received it at Rand.
The paper is the underpinning for results on resistor network inequalities (Reference [4]) which has not been published. A specific example, however, appears inProceedings of the IEEE 51 (1963) 1047–1048. There is also a parallel theory of the abstract assignment problem; every W—L matrix being an assignment matrix.
More is known about minimal non-W—L matrices. U. Peled has found several additional classes of matrices which are also classically known in other contexts. A consequence of a recent matrix theorem is apparently that the degenerate projective planes are the only minimal matrices requiring unequal weights.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R.J. Duffin, “The extremal length of a network”,Journal of Mathematical Analysis and Applications 5 (1962) 200–215.
R.J. Duffin and A.J. Hoffman, The path-cut inequality and networks, mimeographed.
L.R. Ford Jr. and D.R. Fulkerson,Flows in networks (Princeton Univ. Press, Princeton, NJ, 1962).
A. Lehman, Some resistor network inequalities, manuscript.
E.F. Moore and C.E. Shannon, Reliable circuits using less reliable relays,Journal of the Franklin Institute 262 (1956) 204–205.
Author information
Authors and Affiliations
Additional information
Editor's Note: This paper, although written in 1963, was sought for inclusion inMathematical Programming Study 8—Polyhedral Combinatorics, which was dedicated to the memory of D.R. Fulkerson. Unfortunately, an editorial mishap prevented its inclusion. Nevertheless, the historical importance of the paper, the fact that it has been widely referenced and influenced Fulkerson's and others' work in the area has convinced the Editor that it should be published and hence made readily available. Alfred Lehman has given his assent to this despite his reluctance to publish a paper which is not current.
Due to unfortunate circumstances this article was originally published (Mathematical Programming 16(2)(1979) 245–259) without the proof corrections. Thecorrect version is printed herewith. Please use this version when referring to the paper.
The preparation of this paper was supported by the National Science Foundation under grant GP-14.
Rights and permissions
About this article
Cite this article
Lehman, A. On the width—length inequality. Mathematical Programming 17, 403–417 (1979). https://doi.org/10.1007/BF01588263
Issue Date:
DOI: https://doi.org/10.1007/BF01588263