×

Min cost tensions. (English) Zbl 0599.90030

Tensions are functions \(p: E\to {\mathbb{R}}\) defined on the arc set E of a digraph G satisfying \(p(C^+)=p(C^-)\) for all cycles C of G, where \(C^+\) and \(C^-\) are the sets of forward arcs and backward arcs of C, respectively. Given upper bounds \(b_ e\) and costs \(a_ e\) on the edges \(e\in E\), a min cost tension minimizes the linear costs \(\sum p_ ea_ e\), while satisfying \(0\leq p_ e\leq b_ e\), \(e\in E\). Two algorithms to find such a tension, the negative cut algorithm and the shortest augmenting cut algorithm, are given. They represent analogues for the min cost tension problem of the algorithms of Klein (negative cycles) and of Busacker and Gowen (shortest augmenting paths) for the min cost flow problem. Both negative cuts and shortest augmenting cuts can be found by means of capacitated network flows. The author also sketches the use of the min cost tension problem for solving certain totally unimodular linear programs.
Reviewer: A.Gaillard

MSC:

90B10 Deterministic network models in operations research
05C35 Extremal problems in graph theory
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
Full Text: DOI

References:

[1] Berge C., Graphe; et hypergraphes (1973)
[2] Bixby R.E., MOR 5 (3) pp 321– (1980) · Zbl 0442.90095 · doi:10.1287/moor.5.3.321
[3] Burkard R.E., Mathematical Programming Studies 14 pp 32– (1981) · Zbl 0449.90095 · doi:10.1007/BFb0120919
[4] Ford L.R., Flows in networks (1962) · Zbl 0106.34802
[5] Ghouila-Houri A., C.R. Ac. Sciences 250 pp 3931– (1960)
[6] Hamacher H., Discrete Applied Math. 2 pp 27– (1980) · Zbl 0432.90087 · doi:10.1016/0166-218X(80)90052-9
[7] Hamacher H., Math. Systems in Economics 69 (1981)
[8] Hamacher H., Computing 29 pp 113– (1982) · Zbl 0484.05026 · doi:10.1007/BF02249936
[9] Hoffman A.J., Proc. Symposium in Appl. Math 10 pp 113– (1960)
[10] Pla J.M., Math. Progr. 1 pp 275– (1971) · Zbl 0262.90061 · doi:10.1007/BF01584092
[11] Roy B., Cheminement et connexité dans less graphes, application aux problemes d’ordonnancement (1962)
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.