2026-08-07T09:32:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18722 2024-03-06T11:02:33Z ddc:004 open_access

An Improved Approximation Algorithm for the Max-3-Section Problem Katzelnick, Dor Pillai, Aditya Schwartz, Roy Singh, Mohit Approximation Algorithms Semidefinite Programming Max-Cut Max-Bisection We consider the Max--Section problem, where we are given an undirected graph G=(V,E)equipped with non-negative edge weights w: E → R_+ and the goal is to find a partition of V into three equisized parts while maximizing the total weight of edges crossing between different parts. Max-3-Section is closely related to other well-studied graph partitioning problems, e.g., Max-Cut, Max-3-Cut, and Max-Bisection. We present a polynomial time algorithm achieving an approximation of 0.795, that improves upon the previous best known approximation of 0.673. The requirement of multiple parts that have equal sizes renders Max-3-Section much harder to cope with compared to, e.g., Max-Bisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dor Katzelnick and Aditya Pillai and Roy Schwartz and Mohit Singh 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.69 urn:nbn:de:0030-drops-187229 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.69 eng https://creativecommons.org/licenses/by/4.0/legalcode