Scholarlink

<p>The increasing complexity of combinatorial algorithms, especially for solving NP-hard problems like the knapsack problem, has heightened the need for energy- and time-efficient computational solutions. This research optimized two heuristics, namely the greedy algorithm (GA) and dynamic programming algorithm (DPA), with the primary goal of investigating their energy consumption and time complexity. By applying power models and instruction-level parallelism (ILP) techniques to measure and optimize their performance across varying problem sizes, a comprehensive comparison was made. The results demonstrate that the optimized algorithms, particularly GA, exhibit significant improvements in both time and energy efficiency, making them more suitable for large-scale, energy-sensitive applications. In contrast, classical DPA, while providing optimal solutions, shows higher time complexity and energy consumption, especially for larger datasets. However, the optimized DPA addresses these inefficiencies, showing marked improvements in both time and energy use across all instances. This study highlights the critical role of algorithmic optimization in achieving a balance between computational performance and sustainability. The findings contribute to the development of energy-efficient algorithms and underscore the importance of considering both time and energy metrics when solving combinatorial problems.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Optimizing energy efficiency and computational complexity of combinatorial approaches for solving the knapsack problem

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年12月18日

查看全文
  • Bashar Bin Usman,
  • Aderemi Elisha Okeyinka,
  • Ibrahim Abdullahi,
  • Aisha Awal,
  • Adamu Abubakar Isah,
  • Idris Rabiu

摘要

The increasing complexity of combinatorial algorithms, especially for solving NP-hard problems like the knapsack problem, has heightened the need for energy- and time-efficient computational solutions. This research optimized two heuristics, namely the greedy algorithm (GA) and dynamic programming algorithm (DPA), with the primary goal of investigating their energy consumption and time complexity. By applying power models and instruction-level parallelism (ILP) techniques to measure and optimize their performance across varying problem sizes, a comprehensive comparison was made. The results demonstrate that the optimized algorithms, particularly GA, exhibit significant improvements in both time and energy efficiency, making them more suitable for large-scale, energy-sensitive applications. In contrast, classical DPA, while providing optimal solutions, shows higher time complexity and energy consumption, especially for larger datasets. However, the optimized DPA addresses these inefficiencies, showing marked improvements in both time and energy use across all instances. This study highlights the critical role of algorithmic optimization in achieving a balance between computational performance and sustainability. The findings contribute to the development of energy-efficient algorithms and underscore the importance of considering both time and energy metrics when solving combinatorial problems.