Greedy differencing edge-contraction heuristic for the max-cut problem

DOI10.1016/j.orl.2021.02.006OpenAlexW3133894430MaRDI QIDQ2060537

Nikita Leshenko, Refael Hassin

Publication date: 13 December 2021

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2021.02.006

zbMATH Keywords

edge contractiondifferencing methodmax cut

Mathematics Subject Classification ID

Computer science (68-XX) Operations research, mathematical programming (90-XX)

Cites Work

• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Network Design Using Cut Inequalities
• Estimation of Distribution Algorithm for the Max-Cut Problem
• What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
• Fibonacci heaps and their uses in improved network optimization algorithms

This page was built for publication: Greedy differencing edge-contraction heuristic for the max-cut problem