What is known about the complexity of the following problem:
Suppose we have a complete bipartite graph $G(V,E)$ with disjoint sets $C$ and $T$. The candidate vertices, and the target vertices respectively. We want to choose a subset $S\subset C$ of size $2$, a servicing set from the candidates.
For a target vertex $t\in T$, there is a probability $p_t$ that it will issue an order at any turn. Every turn, only one vertex issues an order.
We start at a vertex $s_0\in S$. We wait for the next order to come from a vertex $t_0\in T $, we go to service it. Then, we go to the nearest servicing vertex $s_1$. Next, we get an order from vertex $t_1$, we go from $s_1$ to service $t_1$, then go back to the nearest servicing vertex to $s_2$. We repeat this, going to the nearest vertex servicing vertex in $S$ once you have serviced $t_i$ in turn $i$.
The question is how do we choose $S$ to minimize the average cost from a service node to a target node asymptotically.