A Lasserre SDP Rounding Approximation Algorithm for Max Directed 3-Section

doi:10.26599/TST.2024.9010214

A Lasserre SDP Rounding Approximation Algorithm for Max Directed 3-Section

2025-03-05

0

PRE

AI

DOI：10.26599/TST.2024.9010214

原文链接

原文求助

摘要

En 中文

We consider the Max Directed 3-Section problem, which is closely connected to other well-known graph partition problems, such as Max Cut and Max Bisection. Given an arc-weighted directed graph, the goal of the Max Directed 3-Section problem is to partition the vertex set into three disjoint subsets with equal size, while maximizing the total weight of arcs crossing different vertex subsets. By combining the Lasserre hierarchy with the random hyperplane rounding strategy, we propose a polynomial-time algorithm with approximation ratio of 0.489.

Keyword:

Directed graphs

Programming

Approximation algorithms

Partitioning algorithms

MATLAB

Semi-Definite Programming (SDP)

Lasserre hierarchy

approximation algorithm

Max Cut

Max Bisection

A Lasserre SDP Rounding Approximation Algorithm for Max Directed 3-Section

摘要

期刊

机构

引用论文