A local search algorithm for large maximum weight independent set problems

DOI10.4230/LIPICS.ESA.2022.45MaRDI QIDQ6969637zbMATH OpenFDO

Authors Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe, Nikos Parotsidis, Mauricio G. C. Resende, Quico Spaen

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.45

zbMATH Keywords

GRASPheuristiclocal searchmaximum-weight independent setmetaheuristicpath-relinking

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• A hybrid iterated local search heuristic for the maximum weight independent set problem
• A probabilistic heuristic for a computationally difficult set covering problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Exactly solving the maximum weight independent set problem on large real-world graphs
• Fast local search for the maximum independent set problem
• GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
• GRASP and path relinking for the max-min diversity problem
• Greedy randomized adaptive search procedures
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• New instances for maximum weight independent set from a vehicle routing application
• Optimization by GRASP. Greedy randomized adaptive search procedures
• Paths, Trees, and Flowers
• Reducibility among combinatorial problems
• STABULUS: A technique for finding stable sets in large graphs with tabu search

Cited in

(2)

• Finding 3-swap-optimal independent sets and dominating sets is hard
• Finding near-optimal weight independent sets at scale

This page was built for publication: A local search algorithm for large maximum weight independent set problems

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