A hybrid iterated local search heuristic for the maximum weight independent set problem

DOI10.1007/s11590-017-1128-7zbMath1401.90250OpenAlexW2594540369MaRDI QIDQ1749784

Anand Subramanian, Rian Gabriel S. Pinheiro, Bruno Nogueira

Publication date: 28 May 2018

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-017-1128-7

zbMATH Keywords

metaheuristicsmaximum weight independent setminimum weight vertex coveriterated local searchmaximum weight clique

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (8)

Iterated local search with tabu search for the weighted vertex coloring problem ⋮ An integer program and new lower bounds for computing the strong rainbow connection numbers of graphs ⋮ Towards faster local search for minimum weight vertex cover on massive graphs ⋮ A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic ⋮ A genetic algorithm for the maximum 2-packing set problem ⋮ A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems ⋮ ils-mwis ⋮ On solving the time window assignment vehicle routing problem via iterated local search

Uses Software

• SubMAP

Cites Work

• Unnamed Item
• Solving the maximum vertex weight clique problem via binary quadratic programming
• Breakout local search for maximum clique problems
• Fast local search for the maximum independent set problem
• Approximating the maximum vertex/edge weighted clique using local search
• Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers
• A fast algorithm for the maximum weight clique problem
• Multi-neighborhood tabu search for the maximum weight clique problem
• Genetic algorithmic approach to find the maximum weight independent set of a graph
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• Reducibility among Combinatorial Problems
• A branch-and-price approach for the maximum weight independent set problem
• Efficient algorithms for cluster editing

This page was built for publication: A hybrid iterated local search heuristic for the maximum weight independent set problem