Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10524109 | Operations Research Letters | 2005 | 7 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Oleg A. Prokopyev, Hong-Xuan Huang, Panos M. Pardalos,