An Approach to the Subproblem of the Cutting Angle Method of Global Optimization
Makaleler > Tam Makale · 2005
Yazarlar: Urfat NURİYEV
Journal of Global Optimization, SCI Expanded İndekslerine Giren Dergi, Uluslararası, Wos, 2005, cilt 31, ss 353-370
DOI: 10.1007/s10898-004-1687-x
Özet
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.