A polynomially solvable case of the pooling problem

Natashia Boland, Thomas Kalinowski and Fabian Rigterink ()
Additional contact information
Natashia Boland: Georgia Institute of Technology
Thomas Kalinowski: The University of Newcastle
Fabian Rigterink: The University of Newcastle

Journal of Global Optimization, 2017, vol. 67, issue 3, No 8, 630 pages

Abstract: 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.

Keywords: Pooling problem; Computational complexity; Polynomial-time algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-016-0432-6 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:jglopt:v:67:y:2017:i:3:d:10.1007_s10898-016-0432-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-016-0432-6

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

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