Home/Advances in Computing and Engineering/Article Record
Peer-Reviewed Article August 11, 2024

Enhancing computational efficiency in solving Knapsack problem: insights from algorithmic parallelization and optimization

Are you an author of this work?Link to your sovereign AfriScholar profile
Published in: Advances in Computing and Engineering
Publisher: Academy Publishing Center • Egypt • 2735-5977 • 2735-5985
DOI: https://doi.org/10.21622/ace.2024.04.2.885

Abstract

The Knapsack problem is a combinatorial optimization problem whose exact solution using exhaustive search method is impractical. Hence, the application of approximate algorithms is usually considered when encountering this optimization problem. This study optimized some approximate algorithms: greedy, dynamic programming, and branch-and-bound for the Knapsack problem with specific objectives of evaluating their time and program complexity, comparing efficiencies, and enhancing performance. Our methodology involved utilizing advanced Parallelization techniques to accelerate the implementation of loop-based optimization algorithms by distributing tasks across multiple processing units concurrently. This simultaneous execution minimized computational time, enhanced overall efficiency, and improved scalability, enabling effective resolution of large-scale optimization challenges. Additionally, coefficients for the Knapsack model were generated using a random number generation algorithm. Through analysis and experimental runs using Halstead metrics and time complexity measures, significant improvements in the enhanced algorithms compared to classical approaches were revealed, particularly in terms of program complexity and computational speed. Notably, the enhanced algorithms demonstrated superior time complexity across varying input sizes, indicating their potential as more efficient solutions for the Knapsack Problem. This research contributes to advancing Theoretical Computer Science by offering a new computational approach for tackling intricate knapsack-model-based problems, thereby expanding the toolkit for addressing real world challenges across diverse application areas. Received: 03 June 2024 Accepted: 12 July 2024 Published: 12 August 2024

Download Full Text PDFView at PublisherCrossref RecordCrossref XML

Verified Citation Velocity

Recorded scholarly citations in African and international peer-reviewed literature

1
Total Citations

Citations are continuously tracked and harvested across continental OJS endpoints and OpenAlex feeds.