Anzeige
Erschienen in:
17.02.2020
Approximation algorithms for the maximally balanced connected graph tripartition problem
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2022
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Given a vertex-weighted connected graph \(G = (V, E, w(\cdot ))\), the maximally balanced connected graph k-partition (k-BGP) seeks to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected and the weights of these k parts are as balanced as possible. When the concrete objective is to maximize the minimum (to minimize the maximum, respectively) weight of the k parts, the problem is denoted as max–min k-BGP (min–max k-BGP, respectively), and has received much study since about four decades ago. On general graphs, max–min k-BGP is strongly NP-hard for every fixed \(k \ge 2\), and remains NP-hard even for the vertex uniformly weighted case; when k is part of the input, the problem is denoted as max–min BGP, and cannot be approximated within 6/5 unless P \(=\) NP. In this paper, we study the tripartition problems from approximation algorithms perspective and present a 3/2-approximation for min–max 3-BGP and a 5/3-approximation for max–min 3-BGP, respectively. These are the first non-trivial approximation algorithms for 3-BGP, to our best knowledge.