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

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

0.00 Avg rating0 Votes
Article ID: iaor20031540
Country: United Kingdom
Volume: 29
Issue: 14
Start Page Number: 2087
End Page Number: 2091
Publication Date: Dec 2002
Journal: Computers and Operations Research
Authors: ,
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.

Reviews

Required fields are marked *. Your email address will not be published.