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

DOI10.1016/J.ORL.2021.02.006MaRDI QIDQ2060537zbMATH OpenOpenAlexFDO

Authors Refael Hassin, Nikita Leshenko

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)

Recommendations

• A memetic algorithm for the max-cut problem
• Contraction-based separation and lifting for solving the max-cut problem
• Advanced scatter search for the max-cut problem
• Computational study of a branching algorithm for the maximum \(k\)-cut problem
• Randomized heuristics for the Max-Cut problem

Cites work

• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Estimation of distribution algorithm for the max-cut problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• Network Design Using Cut Inequalities
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO

Cited in

(1)

• An experimental evaluation of semidefinite programming and spectral algorithms for max cut

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2060537)