Fast Local Search for the Maximum Independent Set Problem
Diogo V. Andrade (diogogoogle.com)
Abstract: Given a graph G = (V,E), the independent set problem is that of finding a maximum-cardinality subset S of V such that no two vertices in S are adjacent. We introduce two fast local search routines for this problem. The first can determine in linear time whether a maximal solution can be improved by replacing a single vertex with two others. The second routine can determine in O(mD) time (where D is the highest degree in the graph) whether there are two solution vertices than can be replaced by a set of three. We also present a more elaborate heuristic that successfully applies local search to find near-optimum solutions to a wide variety of instances. We test our algorithms on instances from the literature as well as on new ones proposed in this paper.
Keywords: Maximum independent set, local search, iterated local search, algorithm engineering.
Category 1: Combinatorial Optimization
Category 2: Combinatorial Optimization (Meta Heuristics )
Category 3: Global Optimization (Stochastic Approaches )
Citation: AT&T Labs Research Technical Report, AT&T Labs Research, Florham Park, NJ 07932 USA, 2010.
Entry Submitted: 01/29/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|