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

DOI10.1016/S0305-0548(02)00065-5zbMath1010.90076OpenAlexW2138886673MaRDI QIDQ1867103

Mikhail Y. Kovalyov, Cheng, T. C. Edwin

Publication date: 2 April 2003

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0305-0548(02)00065-5

zbMATH Keywords

computational complexityunconstrained optimizationscheduling

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30) Deterministic scheduling theory in operations research (90B35)

Related Items (5)

Approximation issues of fractional knapsack with penalties: a note ⋮ An alternative approach for proving the NP-hardness of optimization problems ⋮ Complexity of buffer capacity allocation problems for production lines with unreliable machines ⋮ Multi-product lot-sizing and sequencing on a single imperfect machine ⋮ Lot-Sizing and Sequencing on a Single Imperfect Machine

Uses Software

• AMPL

Cites Work

• Unnamed Item
• A survey of results for sequencing problems with controllable processing times
• A bicriterion approach to time/cost trade-offs in sequencing
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: An unconstrained optimization problem is NP-hard given an oracle representation of its objective function: a technical note