A polynomially solvable case of the pooling problem
arXiv:1508.03181 · doi:10.1007/s10898-016-0432-6
Abstract
Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomial time by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border between (strongly) NP-hard and polynomially solvable cases of the pooling problem.
updated references