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 UNSPLITTABLE FLOW

• INSTANCE: Graph $G=\left(V,E\right)$, with edge capacities $c: E\rightarrow Z^{+}$, source vertex s, collection of sinks $t_1,\ldots,t_k$ with associated non-negative integer demands $\rho_1,\ldots,\rho_k$ such that, $\rho_i\le c(e)$ for all $e\in E$ and $i\in[1..k]$.

• SOLUTION: A single s-$t_i$ flow path for each commodity i so that the demands are satisfied and the total flow routed across any edge e is bounded by c(e).

• MEASURE: $\max_{e\in E} f(e)/c(e)$, where f(e) is the total flow routed across e.

  
  

• Good News: Approximable within 3.23 [331].

• Bad News: Not approximable within 3/2$-\varepsilon$ for any $\varepsilon >0$ [325].

• Comment: Approximable within 3.23 also on directed graphs. Variation in which the objective is to maximize the routable demand is approximable within 14. If the objective is to minimize the number of rounds in which all demands are routed, is approximable within 13. The generalized problem in which there are two source vertices is not approximable within 2$-\varepsilon$ [331].