Dergiler / Mathematical and Computational Applications / 2003 / Cilt: 8 - Sayı: 1

On complexity of a global optimization problem

Sayfa
27–34
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

The solution of this problem is also NP-Complete.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez: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.
📊
Temel Bulgular & Veri:For the proof of this fact we formulate another problem which we call "Dominating Subset with Minimal Weight".
💡
Sonuç & Katkı:The solution of this problem is also NP-Complete.
🔬Tür:Modelleme & Sayısal Simülasyon
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Alan Parametreleri

Abstract

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". The solution of this problem is also NP-Complete.

🔖

Bu Makaleye Atıf Yap

NURİYEV, U. G. (2003). On complexity of a global optimization problem. Mathematical and Computational Applications, Cilt: 8 - Sayı: 1, 27–34. https://ajindex.com/articles/280354

📄 Tam Metin PDF Okuyucu

📄

PDF görüntüleyici hazırlanıyor...

Kaynakça (8)

  1. M.Yu. Andramönov, A. M.Rubinov and B. M.Glover, Cutting Angle methods for minimizing increasing convex along rays functions, Research Report 97/7, SITMS, University of Ballarat, 1997
  2. M.Yu. Andramonov, A. M.Rubinov and B. M.Glover, Cutting Angle methods in Global 'Optimization, Applied Mathematics Letters, 12, 95-100, 1999
  3. A. M. Rubinov and M. Andramonov, Minimizing increasing star-shaped functions based on abstract convexity, Journal of Global Optimization, 15, 19-39, 1999
  4. A. M. Rubinov and M. Andramonov, Lipshitz programming via increasing convex along rays functions, Optimization Methods and Software, 10, 763-781, 1999
  5. A. M. Bagirov and A. M. Rubinov, Global minimization of increasing positively homogeneous functions over the unit simplex, Annals of Operations Research, 98,. 171 -187,2000
  6. Dj. A. Babayev, An Exact Method for Solving the Subproblem of the Cutting Angle Method of Global Optimization, In book "Optimization and Related Topicsin Kluwer Academic Publishers, series "Applied Optimization"f Vol. 47,412 -425, Dodrecht/ Boston/ London, December, 2000
  7. R.M.Garey and D.S.Johnson, Computers and Intractability-. A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979
  8. S.Martello and P. Toth. Knapsack Problems: Algorithms and Computer Implementations. John Wiley and Sons, Chichester, 1990.