An approach to the subproblem of the Cutting Angle Method of Global Optimization

Nuriyev U.

JOURNAL OF GLOBAL OPTIMIZATION, cilt.31, ss.353-370, 2005 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 31 Konu: 3
  • Basım Tarihi: 2005
  • Doi Numarası: 10.1007/s10898-004-1687-x
  • Sayfa Sayıları: ss.353-370


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.