Accelerating Reductions Using Graph Neural Networks and a New Concurrent Local Search for the Maximum Weight Independent Set Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Großmann, Ernestine, Langedal, Kenneth, Schulz, Christian
Format:	Preprint
Published:	2024
Subjects:	Optimization and Control Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
by: Großmann, Ernestine, et al.
Published: (2024)

From Maximum Cut to Maximum Independent Set
by: Wu, Chuixiong, et al.
Published: (2024)

Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem
by: Ciccarelli, Fabio, et al.
Published: (2025)

Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem
by: Gao, Xuan-Zhao, et al.
Published: (2024)

Distributed Reductions for the Maximum Weight Independent Set Problem
by: Borowitz, Jannick, et al.
Published: (2025)

On Solving the Set Covering Problem with Conflicts on Sets
by: Montemanni, Roberto, et al.
Published: (2025)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
by: Großmann, Ernestine, et al.
Published: (2026)

A Bregman-Sinkhorn Algorithm for the Maximum Weight Independent Set Problem
by: Haller, Stefan, et al.
Published: (2024)

Computation of Set Tolerances with Applications to the Minimum Spanning Tree Problem
by: Jäger, Gerold, et al.
Published: (2026)

A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems
by: Dong, Yuanyuan, et al.
Published: (2022)

Finding Maximum Weight 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2025)

Finding Maximum Weight 2‐Packing Sets on Arbitrary Graphs
by: Jannick Borowitz, et al.
Published: (2026)

Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems
by: Hu, Chenchuhui
Published: (2024)

The Integrated Vehicle and Pollster Routing Problem
by: Gutiérrez, Sandra, et al.
Published: (2019)

Optimization Models for the Quadratic Traveling Salesperson Problem
by: Chen, Yuxiao, et al.
Published: (2024)

Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
by: Dote, Aki, et al.
Published: (2023)

Conformal Rigidity and Spectral Embeddings of Graphs
by: Gouveia, João, et al.
Published: (2025)

A Modular-Form Framework for Global Optimality in the Asymmetric Traveling-Salesman Problem
by: Gupta, Varsha
Published: (2024)

Monotone Paths on Acyclic 3-Regular Graphs
by: Clément, François, et al.
Published: (2025)

A Clustering-Based Variable Ordering Framework for Relaxed Decision Diagrams for Maximum Weighted Independent Set Problem
by: Nafar, Mohsen, et al.
Published: (2025)

Bilevel Programming for Pebbling Numbers of Lemke Graph Products
by: Pulaj, Jonad, et al.
Published: (2024)

A Vehicle Routing Problem for Human-Centered Electric Mobility
by: Emam, Mostafa, et al.
Published: (2026)

Towards Enabling Learning for Time-Varying finite horizon Sequential Decision-Making Problems*
by: Tiwari, Dhananjay, et al.
Published: (2025)

Performance-Guaranteed Solutions for Multi-Agent Optimal Coverage Problems using Submodularity, Curvature, and Greedy Algorithms
by: Welikala, Shirantha, et al.
Published: (2024)

A Quantum Inspired Bi-level Optimization Algorithm for the First Responder Network Design Problem
by: Karahalios, Anthony, et al.
Published: (2024)

Guarantees for Spontaneous Synchronization on Random Geometric Graphs
by: Abdalla, Pedro, et al.
Published: (2022)

Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator
by: Au, Yu Hin, et al.
Published: (2023)

On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
by: Au, Yu Hin, et al.
Published: (2024)

Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
by: Andrist, Ruben S., et al.
Published: (2023)

Testing Quantum and Simulated Annealers on the Drone Delivery Packing Problem
by: Tarquini, Sara, et al.
Published: (2024)

Low degree sum-of-squares bounds for the stability number: a copositive approach
by: Vargas, Luis Felipe, et al.
Published: (2025)

Branching with a pre-specified finite list of $k$-sparse split sets for binary MILPs
by: Dey, Santanu S., et al.
Published: (2024)

Polyhedral study of a temporal rural postman problem: application in inspection of railway track without disturbing train schedules
by: Buriuly, Somnath, et al.
Published: (2024)

Conformal Rigidity of Graphs: Subdifferentials and Orbit-Isometries
by: Niu, Andrew
Published: (2026)

Exact Flatness Constant for One-Point Convex Bodies and the Discrete Isominwidth Problem: The Planar Case
by: Averkov, Gennadiy, et al.
Published: (2026)

qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem
by: Schuetz, Martin J. A., et al.
Published: (2025)

Cutting plane methods with gradient-based heuristics
by: Bùi, Hòa T., et al.
Published: (2025)

Lower and Upper Bounds for Small Canonical and Ordered Ramsey Numbers
by: Brosch, Daniel, et al.
Published: (2025)

Improvements on Permutation Reconstruction from Minors
by: Ma, Yiming, et al.
Published: (2024)

On disjunction convex hulls by lifting
by: Qu, Yushan, et al.
Published: (2024)