NP-hard problems and test problems for global concave minimization methods

NP-hard problems and test problems for global concave minimization methods

0.00 Avg rating0 Votes
Article ID: iaor19932387
Country: Serbia
Volume: 1
Start Page Number: 45
End Page Number: 50
Publication Date: Dec 1991
Journal: Yugoslav Journal of Operations Research
Authors: ,
Keywords: NP-hard
Abstract:

This paper presents a new method of obtaining hard test problems for global concave minimization problems. The method starts from a three-satisfiability type of problem and it transforms it into a minimization problem over the unit cube with quadratic or cubic concave objective function. An alternative proof of the NP-hardness of such problems is also given.

Reviews

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