𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A strongly polynomial algorithm for the uniform balanced network flow problem

✍ Scribed by Maria Grazia Scutellá

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
565 KB
Volume
81
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

Several balanced optimization

problems have been analysed in the literature. Here, the balanced network flow problem in the uniform case is studied, and it is shown that it can be solved by the Newton's approach in O(n' log3 n) max-flow computations.

The key of the proof is an extension of Radzik's analysis of Newton's method for linear fractional combinatorial optimization problems.

📜 SIMILAR VOLUMES

Balanced network flows. III. Strongly po
Balanced network flows. III. Strongly polynomial augmentation algorithms
✍ Fremuth-Paeger, Christian; Jungnickel, Dieter 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB

We discuss efficient augmentation algorithms for the maximum balanced flow problem which run in O(nm 2 ) time. More explicitly, we discuss a balanced network search procedure which finds valid augmenting paths of minimum length in linear time. The algorithms are based on the famous cardinality match

A strongly polynomial algorithm for the
A strongly polynomial algorithm for the inverse shortest arborescence problem
✍ Hu Zhiquan; Liu Zhenhong 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 909 KB

In this paper an inverse problem of the weighted shortest arborescence problem is discussed. That is. given a directed graph G and a set of nonnegative costs on its arcs. we need to modify those costs as little as possible to ensure that T, a given (.I-arborescence of G, is the shortest one. It is

A deterministic annealing algorithm for
A deterministic annealing algorithm for the minimum concave cost network flow problem
✍ Chuangyin Dang; Yabin Sun; Yuping Wang; Yang Yang 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 292 KB

The existing algorithms for the minimum concave cost network flow problems mainly focus on the singlesource problems. To handle both the single-source and the multiple-source problem in the same way, especially the problems with dense arcs, a deterministic annealing algorithm is proposed in this pap