Abstract
Problem Product Partition differs from the NP-complete problem Partition in that the addition operation is replaced by the multiplication operation. Furthermore it differs from the NP-complete problem Subset Product in that it does not contain the product value B in its input. We prove that problem Product Partition and several of its modifications are NP-complete in the strong sense. Our results imply the strong NP-hardness of a number of scheduling problems with start-time-dependent job processing times and a problem of designing a reliable system with a series-parallel structure. It should be noticed that the strong NP-hardness of the considered optimization problems does not preclude the existence of a fully polynomial time approximation scheme (FPTAS) for them. We present a simple FPTAS for one of these problems.
Original language | English |
---|---|
Pages (from-to) | 601-604 |
Number of pages | 4 |
Journal | European Journal of Operational Research |
Volume | 207 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Dec 2010 |
Keywords
- Complexity theory
- FPTAS
- Scheduling
- Subset Product
- Systems reliability
ASJC Scopus subject areas
- Modelling and Simulation
- Management Science and Operations Research
- Information Systems and Management