# Alternating Delivery Problem

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.

• How long does it take to service a vertex? – JRyan Apr 22 at 17:18