- Title
- A polynomially solvable case of the pooling problem
- Creator
- Boland, Natashia; Kalinowski, Thomas; Rigterink, Fabian
- Relation
- Funding BodyARCGrant NumberLP110200524 http://purl.org/au-research/grants/arc/LP110200524
- Relation
- Journal of Global Optimization Vol. 67, Issue 3, p. 621-630
- Publisher Link
- http://dx.doi.org/10.1007/s10898-016-0432-6
- Publisher
- Springer
- Resource Type
- journal article
- Date
- 2017
- Description
- 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.
- Subject
- pooling problem; computational complexity; polynomial-time algorithm
- Identifier
- http://hdl.handle.net/1959.13/1387313
- Identifier
- uon:32583
- Identifier
- ISSN:0925-5001
- Rights
- This is a post-peer-review, pre-copyedit version of an article published in Journal of Global Optimization. The final authenticated version is available online at: http://dx.doi.org/ 10.1007/s10898-016-0432-6.
- Language
- eng
- Full Text
- Reviewed
- Hits: 1691
- Visitors: 2071
- Downloads: 422
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 243 KB | Adobe Acrobat PDF | View Details Download |