MINIMUM POINT-TO-POINT CONNECTION

• INSTANCE: Graph $G=\left(V,E\right)$, a weight function $w : E \rightarrow N$, a set $S=\{s_1, \ldots, s_p\}$ of sources, and a set $D=\{d_1,\ldots,d_p\}$ of destinations.

• SOLUTION: A point-to-point connection, i.e., a subset $E'\subseteq E$ such that each source-destination pair is connected in E'.

• MEASURE: The weight of the connection, i.e., $\sum_{e \in E'}w(e)$.

  
  

• Good News: Approximable within 2-1/p [197].