刊物主题:Optimization; Operation Research/Decision Theory; Real Functions; Computer Science, general;
出版者:Springer US
ISSN:1573-2916
卷排序:67
文摘
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.