2 Search Results for "Schroeder, Daniel Thilo"

Document
DOI: 10.4230/LIPIcs.SEA.2025.22
Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem

Authors: Ernestine Großmann, Kenneth Langedal, and Christian Schulz

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
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.
Cite as

Ernestine Großmann, Kenneth Langedal, and Christian Schulz. Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gromann_et_al:LIPIcs.SEA.2025.22,
  author =	{Gro{\ss}mann, Ernestine and Langedal, Kenneth and Schulz, Christian},
  title =	{{Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.22},
  URN =		{urn:nbn:de:0030-drops-232600},
  doi =		{10.4230/LIPIcs.SEA.2025.22},
  annote =	{Keywords: Randomized Local Search, Heuristics, Maximum Weight Independent Set, Algorithm Engineering, Parallel Computing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2022.12
Efficient Minimum Weight Vertex Cover Heuristics Using Graph Neural Networks

Authors: Kenneth Langedal, Johannes Langguth, Fredrik Manne, and Daniel Thilo Schroeder

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
Minimum weighted vertex cover is the NP-hard graph problem of choosing a subset of vertices incident to all edges such that the sum of the weights of the chosen vertices is minimum. Previous efforts for solving this in practice have typically been based on search-based iterative heuristics or exact algorithms that rely on reduction rules and branching techniques. Although exact methods have shown success in solving instances with up to millions of vertices efficiently, they are limited in practice due to the NP-hardness of the problem. We present a new hybrid method that combines elements from exact methods, iterative search, and graph neural networks (GNNs). More specifically, we first compute a greedy solution using reduction rules whenever possible. If no such rule applies, we consult a GNN model that selects a vertex that is likely to be in or out of the solution, potentially opening up for further reductions. Finally, we use an improved local search strategy to enhance the solution further. Extensive experiments on graphs of up to a billion edges show that the proposed GNN-based approach finds better solutions than existing heuristics. Compared to exact solvers, the method produced solutions that are, on average, 0.04% away from the optimum while taking less time than all state-of-the-art alternatives.
Cite as

Kenneth Langedal, Johannes Langguth, Fredrik Manne, and Daniel Thilo Schroeder. Efficient Minimum Weight Vertex Cover Heuristics Using Graph Neural Networks. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{langedal_et_al:LIPIcs.SEA.2022.12,
  author =	{Langedal, Kenneth and Langguth, Johannes and Manne, Fredrik and Schroeder, Daniel Thilo},
  title =	{{Efficient Minimum Weight Vertex Cover Heuristics Using Graph Neural Networks}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.12},
  URN =		{urn:nbn:de:0030-drops-165462},
  doi =		{10.4230/LIPIcs.SEA.2022.12},
  annote =	{Keywords: Minimum weighted vertex cover, Maximum weighted independent set, Graph neural networks, Reducing-peeling}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022

  • Refine by Author
  • 2 Langedal, Kenneth
  • 1 Großmann, Ernestine
  • 1 Langguth, Johannes
  • 1 Manne, Fredrik
  • 1 Schroeder, Daniel Thilo
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Randomized local search

  • Refine by Keyword
  • 1 Algorithm Engineering
  • 1 Graph neural networks
  • 1 Heuristics
  • 1 Maximum Weight Independent Set
  • 1 Maximum weighted independent set
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact