2026-07-24T09:35:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23260 2025-10-27T10:36:23Z ddc:004 open_access

Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem Großmann, Ernestine Langedal, Kenneth Schulz, Christian Randomized Local Search Heuristics Maximum Weight Independent Set Algorithm Engineering Parallel Computing The Maximum Weight Independent Set problem is a fundamental NP-hard problem in combinatorial optimization with several real-world applications. Given an undirected vertex-weighted graph, the problem is to find a subset of the vertices with the highest possible weight under the constraint that no two vertices in the set can share an edge. This work presents a new iterated local search heuristic called CHILS (Concurrent Hybrid Iterated Local Search). The implementation of CHILS is specifically designed to handle large graphs of varying densities. CHILS outperforms the current state-of-the-art on commonly used benchmark instances, especially on the largest instances. As an added benefit, CHILS can run in parallel to leverage the power of multicore processors. The general technique used in CHILS is a new concurrent metaheuristic called Concurrent Difference-Core Heuristic that can also be applied to other combinatorial problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ernestine Großmann and Kenneth Langedal and Christian Schulz 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.22 urn:nbn:de:0030-drops-232600 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.22 eng https://creativecommons.org/licenses/by/4.0/legalcode