Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/29613
Title: Product Partition and related problems of scheduling and systems reliability : computational complexity and approximation
Authors: Ng, CT 
Barketau, MS
Cheng, TCE 
Kovalyov, MY
Keywords: Complexity theory
FPTAS
Scheduling
Subset Product
Systems reliability
Issue Date: 2010
Publisher: Elsevier
Source: European journal of operational research, 2010, v. 207, no. 2, p. 601-604 How to cite?
Journal: European journal of operational research 
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.
URI: http://hdl.handle.net/10397/29613
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2010.05.034
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

22
Last Week
0
Last month
1
Citations as of Sep 23, 2017

WEB OF SCIENCETM
Citations

18
Last Week
1
Last month
0
Citations as of Sep 5, 2017

Page view(s)

60
Last Week
1
Last month
Checked on Sep 24, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.