Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MAXIMUM BALANCED CONNECTED PARTITION

• INSTANCE: Connected graph G=(V, E), nonnegative vertex-weight function $w:V\rightarrow N$.
• SOLUTION: A partition $(V_1, V_2)$ of V into nonempty disjoint sets $V_1$ and $V_2$ such that the subgraphs of G induced by $V_1$ and $V_2$ are connected.
• MEASURE: Balance of the partition, i.e., $\min\{w(V_1), w(V_2)\}$, where $w(V')=\sum_{v\in V'} w(v)$.

  
  

• Good News: Approximable within 4/3 [110].
• Bad News: Not approximable with an absolute error guarantee of $\vert V\vert^{1-\varepsilon }$ for any $\varepsilon >0$ [110].
• Comment: Variation in which the objective function is $w(V_1)\cdot w(V_2)$ is approximable within $8-4\sqrt{3}$ [110].