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

Chi To Ng, M. S. Barketau, Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

34 Citations (Scopus)

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 languageEnglish
Pages (from-to)601-604
Number of pages4
JournalEuropean Journal of Operational Research
Volume207
Issue number2
DOIs
Publication statusPublished - 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

Cite this