An unconstrained optimization problem is NP-hard given an oracle representation of its objective function: A technical note

Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

The problem of unconstrained minimization of a piecewise linear function of one variable is shown to be NP-hard given an oracle representation of the function. This result can be applied to establish the NP-hardness of the scheduling problem with controllable job processing times given an oracle representation of the scheduling cost. The computational complexity of this scheduling problem has remained unknown for more than 20 years. We consider the problem of unconstrained optimization from the perspective of classifying its computational complexity, and show that it is NP-hard. This result enables us to establish the NP-hardness of the scheduling problem with controllable job processing times, whose computational complexity status has remained unknown for a long time.
Original languageEnglish
Pages (from-to)2087-2091
Number of pages5
JournalComputers and Operations Research
Volume29
Issue number14
DOIs
Publication statusPublished - 1 Jan 2002

Keywords

  • Computational complexity
  • Scheduling
  • Unconstrained optimization

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this