Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers

摘要

This paper extends the recently introduced Phased Local Search (PLS) maximum clique algorithm to unweighted/weighted maximum independent set and minimum vertex cover problems. PLS is a stochastic reactive dynamic local search algorithm that interleaves sub-algorithms which alternate between sequences of iterative improvement, during which Suitable vertices are added to the current sub-graph, and plateau search, during which vertices of the Current sub-graph are swapped with vertices not contained in the Current sub-graph. These sub-algorithms differ in their vertex selection techniques and also in the perturbation mechanism used to overcome search stagnation. PLS has no problem instance dependent parameters and achieves state-of-the-art performance over a large range of the commonly used DIMACS and other benchmark instances.