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: | Pardalos Panos M., Prokopyev Oleg A., Huang Hong-Xuan |
Keywords: | combinatorial analysis |
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.