An Efficient Riemannian Gradient Based Algorithm for Max-Cut Problems

Mohamad Mahdi Mohades

doi:10.1109/TCSII.2021.3104251

An Efficient Riemannian Gradient Based Algorithm for Max-Cut Problems

2022-03-01

1

OA

AI

M

Mohamad Mahdi Mohades

M

Mohammad Hossein Kahaei *

DOI：10.1109/TCSII.2021.3104251

Original

Original request for help

Save

Abstract

En 中文

The max-cut problem addresses the problem of finding a cut for a graph that splits the graph into two subsets of vertices so that the number of edges between these two subsets is as large as possible. However, this problem is NP-Hard, which may be solved by suboptimal algorithms. In this brief, we propose a fast and accurate Riemannian optimization algorithm for solving the max-cut problem. To do so, we develop a gradient descent algorithm and prove its convergence. Our simulation results show that the proposed method is extremely efficient on some already-investigated graphs. Specifically, our method is on average 35 times faster than the best well-known techniques with slightly losing the performance, which is on average 0.96 of the max-cut value of the others.

Keywords:

Approximation algorithms

Manifolds

Convergence

Routing

Runtime

Clustering algorithms

Circuits and systems

Max-cut problem

manifold optimization

polynomial time

NP-hard

An Efficient Riemannian Gradient Based Algorithm for Max-Cut Problems

Abstract

Journal

Organization