排序方式: 共有3条查询结果,搜索用时 15 毫秒
1
1.
Michael Holzhauser Sven O. Krumke Clemens Thielen 《Journal of Combinatorial Optimization》2017,33(4):1226-1256
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]\) 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}}\)-hard to solve and approximate in this case. 相似文献
2.
3.
Bazgan Cristina Herzel Arne Ruzika Stefan Thielen Clemens Vanderpooten Daniel 《Journal of Combinatorial Optimization》2022,43(5):1328-1358
Journal of Combinatorial Optimization - In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is... 相似文献
1