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

DOI10.1016/S0305-0548(02)00065-5MaRDI QIDQ1867103zbMATH OpenOpenAlexFDO

Authors M. Y. Kovalyov, T. C. Edwin Cheng

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 complexityschedulingunconstrained optimization

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5799870
• Complexity of a scheduling problem with controllable processing times
• Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard.
• Checking local optimality in constrained quadratic programming is NP- hard
• \(NP\)-hardness of linear multiplicative programming and related problems

Cites work

• A bicriterion approach to time/cost trade-offs in sequencing
• A survey of results for sequencing problems with controllable processing times
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

Cited in

(6)

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

Describes a project that uses

Uses Software

• AMPL

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1867103)