On Bottleneck and $k$-sum versions of the process network synthesis problem


Z. Blázsik, Cs. Holló, B. Imreh, Cs. Imreh, Z. Kovács




In this paper, we deal with a special case of the Minsum problem, the Process Network Synthesis (PNS) problem. We show that the $k$-sum version of the PNS problem is well-solvable, and thus, the PNS problem is such a particular case of the Minsum problem which is NP-complete while its $k$-sum version is well-solvable for a fixed $k$.