"Product Partition" and related problems of scheduling and systems reliability: Computational complexity and approximation

C.T. Ng, M.S. Barketau, T.C.E. Cheng and Mikhail Y. Kovalyov

European Journal of Operational Research, 2010, vol. 207, issue 2, 601-604

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.

Keywords: Complexity; theory; Scheduling; Subset; Product; FPTAS; Systems; reliability (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00390-5
Full text for ScienceDirect subscribers only

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:eee:ejores:v:207:y:2010:i:2:p:601-604

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().