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

Nuriyev U.

JOURNAL OF GLOBAL OPTIMIZATION, vol.31, no.3, pp.353-370, 2005 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 31 Issue: 3
  • Publication Date: 2005
  • Doi Number: 10.1007/s10898-004-1687-x
  • Page Numbers: pp.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.