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)

MINIMUM QUOTIENT CUT

• INSTANCE: Graph $G=\left(V,E\right)$, a vertex-weight function $w:V\rightarrow N$, and an edge-cost function $c : E \rightarrow N$.

• SOLUTION: A cut C, i.e., a subset $C \subseteq V$.

• MEASURE: The quotient of the cut, i.e.,
  
  $$\frac{c(C)}{\min\{w(C),w(V-C)\}}$$
  
  
  where c(C) denotes the sum of the costs of the edges (u,v) such that either $u \in C$ and $v \not\in C$ or $u \not\in C$ and $v \in C$ and, for any subset $V' \subseteq V$, w(V') denotes the sum of the weights of the vertices in V'.

  
  

• Good News: Approximable within $O(\log \vert V\vert)$ [345].

• Comment: Also called Minimum Flux Cut. Admits a PTAS for planar graphs [395]. The generalization to hypergraphs, also called Minimum Net Expansion, is approximable within $O(\log \vert E\vert)$ in the uniform vertex-weight case [368]. Other approximation algorithms for hypergraph partitioning problems are contained in [368].