Algorithms with guarantee value for knapsack problems

Guler A., Nuriyev U., Berberler M. E., Nuriyeva F.

OPTIMIZATION, cilt.61, sa.4, ss.477-488, 2012 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 61 Sayı: 4
  • Basım Tarihi: 2012
  • Doi Numarası: 10.1080/02331934.2011.617818
  • Dergi Adı: OPTIMIZATION
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.477-488
  • Anahtar Kelimeler: integer programming, knapsack problems, greedy algorithms, guarantee value, complementary problem, SUM
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

In this study one-dimensional knapsack problems (KP), which have many applications in technical and economic areas, are studied; then greedy algorithms are discussed for these problems. Guarantee values of these algorithms are calculated in order to determine how the results, returned by the algorithms, are close to optimal solutions. Furthermore, complementary problems for integer maximization KP and bounded integer maximization KP are defined; and it is aimed to improve the guarantee values, which have been calculated before, in terms of the complementary problems.