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.

  • $\begingroup$ How long does it take to service a vertex? $\endgroup$ – JRyan Apr 22 '19 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.