Maximum flows in generalized processing networks

Michael Holzhauser (), Sven O. Krumke () and Clemens Thielen ()
Additional contact information
Michael Holzhauser: University of Kaiserslautern
Sven O. Krumke: University of Kaiserslautern
Clemens Thielen: University of Kaiserslautern

Journal of Combinatorial Optimization, 2017, vol. 33, issue 4, No 4, 1226-1256

Abstract: Abstract Processing networks (cf. Koene in Minimal cost flow in processing networks: a primal approach, 1982) and manufacturing networks (cf. Fang and Qi in Optim Methods Softw 18:143–165, 2003) are well-studied extensions of traditional network flow problems that allow to model the decomposition or distillation of products in a manufacturing process. In these models, so called flow ratios $$\alpha _e \in [0,1]$$ α e ∈ [ 0 , 1 ] are assigned to all outgoing edges of special processing nodes. For each such special node, these flow ratios, which are required to sum up to one, determine the fraction of the total outgoing flow that flows through the respective edges. In this paper, we generalize processing networks to the case that these flow ratios only impose an upper bound on the respective fractions and, in particular, may sum up to more than one at each node. We show that a flow decomposition similar to the one for traditional network flows is possible and can be computed in strongly polynomial time. Moreover, we show that there exists a fully polynomial-time approximation scheme (FPTAS) for the maximum flow problem in these generalized processing networks if the underlying graph is acyclic and we provide two exact algorithms with strongly polynomial running-time for the problem on series–parallel graphs. Finally, we study the case of integral flows and show that the problem becomes $${\mathcal {NP}}$$ NP -hard to solve and approximate in this case.

Keywords: Algorithms; Complexity; Maximum flow problem; Processing networks (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0031-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:4:d:10.1007_s10878-016-0031-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0031-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().