mlsanityData to 14 Oct 2026

A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut

arXiv 2505.13405 ↗First posted 19 May 2025cs.LG stat.MLcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

The Maximum Cut (MaxCut) problem is NP-Complete, and obtaining its optimal solution is NP-hard in the worst case. As a result, heuristic-based algorithms are commonly used, though their design often requires significant domain expertise. More recently, learning-based methods trained on large (un)labeled datasets have been proposed; however, these approaches often struggle with generalizability and scalability. A well-known approximation algorithm for MaxCut is the Goemans-Williamson (GW) algorithm, which relaxes the Quadratic Unconstrained Binary Optimization (QUBO) formulation into a semidefinite program (SDP). The GW algorithm then applies hyperplane rounding by uniformly sampling a random hyperplane to convert the SDP solution into binary node assignments. In this paper, we propose a training-data-free approach based on a non-episodic reinforcement learning formulation, in which an agent learns to select improved rounding hyperplanes that yield better cuts than those produced by the GW algorithm. By optimizing over a Markov Decision Process (MDP), our method consistently achieves better cuts across large-scale graphs with varying densities and degree distributions.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 6 of its 19 references that are in the map. First posted on arXiv 19 May 2025.

Builds on

6 of 19 references.

References · 6

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Continuous control with deep reinforcement learningcited by 3,407
  3. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  4. 2019Exploratory Combinatorial Optimization with Reinforcement Learningcited by 82
  5. 2020Learning What to Defer for Maximum Independent Setscited by 54
  6. 2024Differentiable Quadratic Optimization For The Maximum Independent Set Problemcited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Theoretical Foundations of max@k Reinforcement Learning
  2. 2026Learning to Cut: Reinforcement Learning for Benders Decomposition
  3. 2025Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming
  4. 2026Maximum Likelihood Reinforcement Learning
  5. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes
  6. 2024Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming
  7. 2025The Best of N Worlds: Aligning Reinforcement Learning with Best-of-N Sampling via max@k Optimisation
  8. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning