I'm considering the following basic assignment problem: a group of $n$ people is to be assigned, in one-to-one fashion, a set of $n$ jobs. Write $C_{ij}$ for the cost incurred when person $i$ gets assigned to job $j$. I shall assume that the $C_{ij}$ are iid exponentially distributed.
I consider two greedy algorithms.
- Algorithm A assigns to person 1 the job that results in the least cost, then chooses for person 2 the cheapest job out of the remaining $n-1$ options, and so on.
- Algorithm B considers all $n^2$ cost values, finds the minimal pair $(i_1,j_1)$, and assigns person $i_1$ to job $j_1$, so that $(n-1)^2$ values remain, finds the minimal pair $(i_2,j_2)$ out of those, and so on.
I claim that both algorithms have the same expected cost. By noting that the minimum of $k$ exponentially distributed variables of rate $\mu$ is itself exponentially distributed of rate $k\mu$, one shows that algorithm A has expected cost $$E(A) = 1 + \frac{1}{2} + \cdots + \frac{1}{n}.$$ Now for algorithm B. The minimal cost $C_{(i_1,j_1)}$ is exponentially distributed of rate $n^2$. By memorylessness, $C_{(i_2,j_2)}$ is equal to $C_{(i_1,j_1)}$ plus an exponential of rate $(n-1)^2$, and so on, so that \begin{equation} \begin{split} E(B) &= E(C_{(i_1,j_1)}) + \cdots + E(C_{(i_n,j_n)}) \\ &= n \cdot \frac{1}{n^2} + (n-1)\cdot \frac{1}{(n-1)^2} + \cdots + 1 \cdot \frac{1}{1^2}\\ &= \frac{1}{n} + \frac{1}{n-1} + \cdots + 1. \end{split} \end{equation}
My intuition expecting the global approach to typically be more efficient, I was surprised by this outcome, and attempted to simulate the situation. Let's implement the greedy algorithms in Python.
def GreedyA(arr):
total_cost = 0
for _ in range(n - 1):
job_choices = arr[0]
cheapest = job_choices.argmin()
total_cost += job_choices[cheapest]
arr = np.delete(arr, 0, axis = 0)
arr = np.delete(arr, cheapest, axis = 1)
return total_cost
def GreedyB(arr):
total_cost = 0
for _ in range(n - 1):
x, y = np.unravel_index(arr.argmin(), arr.shape)
total_cost += arr[x][y]
arr = np.delete(arr, x, axis = 0)
arr = np.delete(arr, y, axis = 1)
return total_cost
I now run the simulation, arbitrarily picking $n$ to be $10$, making the math predict that $E(A) = E(B) \approx 2.9$.
values_A = []
values_B = []
n = 10
iterations = 10000
for _ in range(iterations):
costs = np.random.exponential(size = (n, n), scale = 1)
outcomeA = GreedyA(costs)
outcomeB = GreedyB(costs)
values_A.append(outcomeA)
values_B.append(outcomeB)
I'll plot the results.
Both algorithms seem to come out more efficiently than expected, as nearly all simulation resulted in a cost significantly below $2.9$. In addition, in line with my doubts, algorithm B seems to perform much better than algorithm A.
Question. What is going wrong in my analysis?
