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 SINGLE-SINK EDGE INSTALLATION

• INSTANCE: Graph $G=\left(V,E\right)$, length function $l:E \rightarrow N$, set of sources $S\subseteq V$, sink $t\in V$, demand function $d:S\rightarrow Z^+$, finite set of cable types where each cable type is specified by its capacity and its cost per unit length.

• SOLUTION: A network of cables in the graph, consisting of an integral number of each cable type for each edge in G, that routes all the demands at the sources to the sink. The demand of each source must follow a single path from source to sink.

• MEASURE: The total cost of building the network of cables.

  
  

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

• Comment: Variations in which there are multiple sinks (a generalization of MINIMUM GENERALIZED STEINER NETWORK) or just a number k of the sources need to be connected to the sink (a generalization of MINIMUM K-STEINER TREE) is also approximable within $O(\log^2 \vert V\vert)$ [49]. Approximable within $O(\log D)$, where $D=\sum_{s\in S} d(s)$, for points in the Euclidean plane. Restricted version where the network to be designed must be a two-level tree (so that every path from a source to the sink consists of at most two edges) is approximable within $O(\log \vert V\vert)$ [427].