Browsing by Subject "Approximation algorithms"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Comparative analysis of particle swarm optimization varying the inertia factor(Department of Computer Science and Information Technology, 2013) Aryal, SandeepFinding a sub-optimal solution to a difficult problem sometimes is better than finding the optimal one. It results in the reduction of cost in terms of time and feasibility. Approximation algorithms do the same thing. Among the different optimization techniques for different optimization problems, approximation algorithms help in finding approximate to optimal results. In this dissertation, an implementation of the Particle Swarm Optimization, an approximation algorithm, has been provided. Different parameters as found in the Particle Swarm Optimization have been varied. The impact of the variation in the algorithm has been studied with respect to three standard benchmark equations namely, Parabola, Rosenbrock and Griewank and statistically analyzed afterwards. The main area of this work however, goes through the variation of the Inertia factor in the algorithm. This factor has been varied with the values that go through arithmetic, geometric and harmonic sequence. The impact or the resulting effects of the variations for the benchmark equations have been provided with the statistical analysis of the results. The work then gives a suggestive approach on the selection of progression when varying Inertia factor through arithmetic, geometric and harmonic sequence in the simplest form of Particle Swarm Optimization algorithm. Keywords: Approximation Algorithms, Swarm Intelligence, Particle Swarm Optimization, Inertia Weight, Mathematical Progressions,Item Comparative Evaluation of Minimum Degree Based Approximation Algorithms for Minimum Vertex Cover Problem(Department of Computer Science and Information Technology, 2017) Mahato, Santosh KumarMinimum vertex cover(MVC) problem is a NP Complete optimization problem that attracts many researchers due to its wide range of application in real life problems. As MVC is NPcomplete, there are no any algorithm that finds optimal solution to MVC problem in polynomial time. Numerous of approaches have been proposed among which approximation approach is much favored in the field of MVC as it guarantees to give a solution that is near to optimal or sub optimal solution. There is a number of MVC algorithm based on approximation approaches that constructs vertex cover .This Dissertation work is focused on a comparative study of three recent approximation approach based algorithms ,NOVCA,CSSA and NMVSA. The performance of each algorithm is measured in terms of approximation ratio and step count. Here step count is used as second performance metrics because the performance differences in approximation ratio of all the algorithms are relatively small. In the dissertation work, benchmark graph datasets are used for the comparison of algorithms and an extensive analysis have been provided to help the selection of efficient algorithm.