Nam Le

Maximal Cut (Max-Cut)

Nam Le
Table of Contents

Maximal Cut (Max-Cut) #

The Maximal Cut problem is to partition the vertices of a graph into two sets to maximize the number of edges between them. It’s a fundamental problem in combinatorial optimization.

Recent Literature #

  1. Learning Combinatorial Optimization Algorithms over Graphs. NeurIPS, 2017. paper

    Dai, Hanjun and Khalil, Elias B and Zhang, Yuyu and Dilkina, Bistra and Song, Le

  2. Exploratory Combinatorial Optimization with Reinforcement Learning. AAAI, 2020. paper

    LBarrett, Thomas and Clements, William and Foerster, Jakob and Lvovsky, Alex.

  3. Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs. NeurIPS, 2020. paper

    Karalias, Nikolaos and Loukas, Andreas

  4. Reversible Action Design for Combinatorial Optimization with Reinforcement Learning Arxiv, 2021. paper

    Yao, Fan and Cai, Renqin and Wang, Hongning

  5. LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation ICML, 2022. paper, code

    Ireland, David and G. Montana

  6. Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration Arxiv, 2022. paper, code

    Barrett, Thomas D and Parsonson, Christopher WF and Laterre, Alexandre

  7. Revisiting Sampling for Combinatorial Optimization ICML, 2023. paper

    Sun, Haoran, Goshvadi Katayoon,Nova Azade,Schuurmans Dale and Dai Hanjun.

  8. Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods NeurIPS, 2023. paper

    Caramanis, Constantine and Fotakis, Dimitris and Kalavasis, Alkis and Kontonis, Vasilis and Tzamos, Christos

  9. Neural Improvement Heuristics for Graph Combinatorial Optimization Problems TNNLS, 2023. journal

    Andoni I. Garmendia, Josu Ceberio, Alexander Mendiburu

  10. Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets NeurIPS, 2023. paper, code

    Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, Ling Pan

  11. Variational Annealing on Graphs for Combinatorial Optimization NeurIPS, 2023. paper, code

    Sanokowski, Sebastian and Berghammer, Wilhelm Franz and Hochreiter, Sepp and Lehner, Sebastian

  12. DISCS: A Benchmark for Discrete Sampling NeurIPS, 2023. paper

    Katayoon Goshvadi, Haoran Sun, Xingchao Liu, Azade Nova, Ruqi Zhang, Will Sussman Grathwohl, Dale Schuurmans, Hanjun Dai

  13. MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization IJCAl, 2024. paper, code

    Andoni I. Garmendia, Quentin Cappart, Josu Ceberio, Alexander Mendiburu

  14. Controlling Continuous Relaxation for Combinatorial Optimization NeurIPS, 2024. paper

    Yuma Ichikawa

  15. Efficient Combinatorial Optimization via Heat Diffusion NeurIPS, 2024. paper

    Hengyuan Ma, Wenlian Lu, Jianfeng Feng

  16. ⭐COExpander: Adaptive Solution Expansion for Combinatorial Optimization ICML, 2025. paper, code

    Jiale Ma and Wenzheng Pan and Yang Li and Junchi Yan

  17. ⭐ML4CO-Bench-101: Benchmark Machine Learning for Classic Combinatorial Problems on Graphs NeurIPS, 2025. paper, code

    Jiale Ma and Wenzheng Pan and Yang Li and Junchi Yan

Tags:
Categories: