A Heuristic Approach for Minimum Set Cover Problem
Journal Title: International Journal of Advanced Research in Artificial Intelligence(IJARAI) - Year 2015, Vol 4, Issue 6
Abstract
The Minimum Set Cover Problem has many prac-tical applications in various research areas. This problem belongs to the class of NP-hard theoretical problems. Several approxima-tion algorithms have been proposed to find approximate solutions to this problem and research is still going on to optimize the solution. This paper studies the existing algorithms of minimum set cover problem and proposes a heuristic approach to solve the problem using modified hill climbing algorithm. The effectiveness of the approach is tested on set cover problem instances from OR-Library. The experimental results show the effectiveness of our proposed approach.
Authors and Affiliations
Fatema Akhter
Keywords
Related Articles
- EP ID EP100564
- DOI 10.14569/IJARAI.2015.040607
- Views 145
- Downloads 0
Hybrid Metaheuristics for the Unrelated Parallel Machine Scheduling to Minimize Makespan and Maximum Just-in-Time Deviations
This paper studies the unrelated parallel machine scheduling problem with three minimization objectives – makespan, maximum earliness, and maximum tardiness (MET-UPMSP). The last two objectives combined are related...
Applying Inhomogeneous Probabilistic Cellular Au-tomata Rules on Epidemic Model
This paper presents some of the results of our probabilis¬tic cellular automaton (PCA) based epidemic model. It is shown that PCA performs better than deterministic ones. We consider two possible ways of interactio...
Military Robotics: Latest Trends and Spatial Grasp Solutions
A review of some latest achievements in the area of military robotics is given, with main demands to management of advanced unmanned systems formulated. The developed Spatial Grasp Technology, SGT, capable of satis...
Parameter Optimization for Nadaraya-Watson Kernel Regression Method with Small Samples
Many current regression algorithms have unsatisfactory prediction accuracy with small samples. To solve this problem, a regression algorithm based on Nadaraya-Watson kernel regression (NWKR) is proposed. The propos...
Driver’s Awareness and Lane Changing Maneuver in Traffic Flow based on Cellular Automaton Model
Effect of driver’s awareness (e.g., to estimate the speed and arrival time of another vehicle) on the lane changing maneuver is discussed. “Scope awareness” is defined as the visibility which is required for the dr...