On characterization of maximal independent sets via quadratic optimization

Foad Mahdavi Pajouh, Balabhaskar Balasundaram, Oleg A. Prokopyev

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

This article investigates the local maxima properties of a box-constrained quadratic optimization formulation of the maximum independent set problem in graphs. Theoretical results characterizing binary local maxima in terms of certain induced subgraphs of the given graph are developed. We also consider relations between continuous local maxima of the quadratic formulation and binary local maxima in the Hamming distance-1 and distance-2 neighborhoods. These results are then used to develop an efficient local search algorithm that provides considerable speed-up over a typical local search algorithm for the binary Hamming distance-2 neighborhood.

Original languageEnglish
Pages (from-to)629-644
Number of pages16
JournalJournal of Heuristics
Volume19
Issue number4
DOIs
StatePublished - Aug 2013

Keywords

  • Independence number
  • Local maxima
  • Quadratic optimization

Fingerprint

Dive into the research topics of 'On characterization of maximal independent sets via quadratic optimization'. Together they form a unique fingerprint.

Cite this