An Approach to the Subproblem of the Cutting Angle Method of Global Optimization
Articles > Article · 2005
Authors: Urfat NURİYEV
Journal of Global Optimization, Journal Indexed in SCI Expanded, International, WoS, 2005, vol 31, pp 353-370
DOI: 10.1007/s10898-004-1687-x
Summary
The solution of the Subproblem of the Cutting Angle Method of Global Optimization for problems of minimizing increasing positively homogeneous of degree one functions is proved to be NP-Complete. For the proof of this fact we formulate another problem which we call "Dominating Subset with Minimal Weight". This problem is also NP-Complete. An O(n(2))-time algorithm is presented for approximate solution of Dominant Subset with Minimal Weight Problem. This problem can be expressed as a kind of Assignment Problem in which it is allowed to assign multiple tasks to a single processor. Experimental analysis of the algorithm is performed using the program implemented in ANSI-C. The results of the analysis show the efficiency of the proposed algorithm.