Technical Note—A Dominance Theorem for the Stochastic Queue Median Problem

In this note we prove a dominance property of the set of Hakimi medians for the Stochastic Queue Median (SQM) problem on a network. The SQM minimizes the average response time of a mobile server to a random request for service which occurs in accordance with independent Poisson processes from nodes of a network. We constructively find two strictly positive ranges of the Poisson arrival rate over which a subset of the Hakimi medians will dominate all other locations on the network. These ranges are at the extremes of the arrival rates in which the SQM problem is feasible. Specifically, these intervals are server utilization ranges covering zero and one, respectively.