On complexity of unconstrained hyperbolic 0–1 programming problems

On complexity of unconstrained hyperbolic 0–1 programming problems

0.00 Avg rating0 Votes
Article ID: iaor20051947
Country: Netherlands
Volume: 33
Issue: 3
Start Page Number: 312
End Page Number: 318
Publication Date: May 2005
Journal: Operations Research Letters
Authors: , ,
Keywords: combinatorial analysis
Abstract:

Single- and multiple-ratio unconstrained hyperbolic 0–1 programming problems are considered. We prove that checking whether these problems have a unique solution is NP-hard. Furthermore, we show that finding the global maximizer of problems with unique solution remains NP-hard. We also discuss complexity of local search and approximability for multiple-ratio problems.

Reviews

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