Stabilizer Approximation III: Maximum Cut

We apply the stabilizer formalism to the Maximum Cut problem, and obtain a new greedy construction heuristic. It turns out to be an elegant synthesis of the edge-contraction and differencing edge-contraction approaches. Utilizing the relation between the Maximum Cut problem and the Ising model, the...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-05
Main Authors: Wu, Chuixiong, Wang, Jianan, Zuo, Fen
Format: Article
Language:English
Subjects:
Apexes
Approximation
Heuristic
Mathematical analysis
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We apply the stabilizer formalism to the Maximum Cut problem, and obtain a new greedy construction heuristic. It turns out to be an elegant synthesis of the edge-contraction and differencing edge-contraction approaches. Utilizing the relation between the Maximum Cut problem and the Ising model, the approximation ratio of the heuristic is easily found to be at least \(1/2\). Moreover, numerical results show that the heuristic has very nice performance for graphs with about 100 vertices.
ISSN:2331-8422