-

 

 

 




Optimization Online





 

Fast Local Search for the Maximum Independent Set Problem

Diogo V. Andrade (diogo***at***google.com)
Mauricio G. C. Resende (mgcr***at***research.att.com)
Renato F. Werneck (renatow***at***microsoft.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.

Download: [PDF]

Entry Submitted: 01/29/2008
Entry Accepted: 02/01/2008
Entry Last Modified: 07/15/2010

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society