ND46 M INIMUM S INGLE -S INK E DGE I NSTALLATION

     
• I NSTANCE : Graph , length function , set of sources , sink , demand function , finite set of cable types where each cable type is specified by its capacity and its cost per unit length.
• S OLUTION : 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.
• M EASURE : The total cost of building the network of cables.

• Comment: Approximable within , where , 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 [ 314 ].