TY - JOUR
T1 - On characterization of maximal independent sets via quadratic optimization
AU - Mahdavi Pajouh, Foad
AU - Balasundaram, Balabhaskar
AU - Prokopyev, Oleg A.
PY - 2013/8
Y1 - 2013/8
N2 - 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.
AB - 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.
KW - Independence number
KW - Local maxima
KW - Quadratic optimization
UR - http://www.scopus.com/inward/record.url?scp=84880916206&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84880916206&partnerID=8YFLogxK
U2 - 10.1007/s10732-011-9171-5
DO - 10.1007/s10732-011-9171-5
M3 - Article
AN - SCOPUS:84880916206
SN - 1381-1231
VL - 19
SP - 629
EP - 644
JO - Journal of Heuristics
JF - Journal of Heuristics
IS - 4
ER -