SOLVING NP-HARD OPTIMIZATION PROBLEMS: A COMPARISON OF CLASSICAL APPROXIMATION ALGORITHMS AND MODERN METAHEURISTIC AND LEARNING-BASED METHODS

Abstract

Many optimization problems of practical importance in computer science are NP-hard, meaning that no polynomial-time algorithm is known that solves them exactly [1,2]. Because exact solution is computationally infeasible for large instances, the discipline has developed two broad families of practical alternatives. Classical approximation algorithms sacrifice optimality in exchange for polynomial running time while providing a provable guarantee on the quality of the solution returned [2,3]. Modern metaheuristics, including simulated annealing, genetic algorithms and ant colony optimization, abandon formal guarantees in favour of flexible stochastic search that frequently produces excellent solutions in practice [4,5]. More recently, learning-based methods have been proposed which train neural models to construct or improve solutions directly from problem instances [6]. This thesis compares these paradigms with respect to solution quality, theoretical guarantees, computational cost and generality. It argues that approximation algorithms remain essential where worst-case assurance is required, that metaheuristics dominate where empirical performance on large instances is the governing criterion, and that a hybrid strategy—using approximation results as a principled starting point for metaheuristic refinement—offers the most robust approach for practical deployment [3,5,7]..