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

DOI10.1007/S11590-017-1128-7MaRDI QIDQ1749784zbMATH OpenOpenAlexFDO

Authors Bruno Nogueira, Rian G. S. Pinheiro, A. Subramanian

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)

Recommendations

• A new heuristic algorithm to solve the maximum independent set problem
• Multi-neighborhood tabu search for the maximum weight clique problem
• A branch-and-price approach for the maximum weight independent set problem
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• Genetic algorithmic approach to find the maximum weight independent set of a graph

Cites work

• scientific article; zbMATH DE number 1786225 (Why is no real title available?)
• A branch-and-price approach for the maximum weight independent set problem
• A fast algorithm for the maximum weight clique problem
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• Approximating the maximum vertex/edge weighted clique using local search
• Breakout local search for maximum clique problems
• Efficient algorithms for cluster editing
• Fast local search for the maximum independent set problem
• Genetic algorithmic approach to find the maximum weight independent set of a graph
• Multi-neighborhood tabu search for the maximum weight clique problem
• Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers
• Reducibility among combinatorial problems
• Solving the maximum vertex weight clique problem via binary quadratic programming

Cited in

(15)

• Solving the set packing problem via a maximum weighted independent set heuristic
• An integer program and new lower bounds for computing the strong rainbow connection numbers of 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 new heuristic algorithm to solve the maximum independent set problem
• Genetic algorithmic approach to find the maximum weight independent set of a graph
• Towards faster local search for minimum weight vertex cover on massive graphs
• A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems
• Integer linear programming models and greedy heuristic for the minimum weighted independent dominating set problem
• Iterated local search with tabu search for the weighted vertex coloring problem
• A branch-and-price approach for the maximum weight independent set problem
• ils-mwis
• scientific article; zbMATH DE number 4064507 (Why is no real title available?)
• A metaheuristic algorithm for large maximum weight independent set problems
• On solving the time window assignment vehicle routing problem via iterated local search

Describes a project that uses

Uses Software

• SubMAP

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1749784)