# Greedy algorithms for assignment problems --- prediction doesn't match simulation

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{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}$$$$

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)

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)


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?

• Obviously, in algo A the result much depends on the order of processing people. On each of its greedy steps, you are first selecting (randomly?) a man and not selecting a job yet: job has no "vote" meanwhile. Of course, this algo is expected to be worse than algo B.
– ttnphns
Jan 14, 2021 at 11:37
• @ttnphns Of course one can concoct situations in which algorithm A outperforms algorithm B. Take for instance the matrix $\Big(\begin{smallmatrix} 1 & 3 & 3 \\ 3 & 1 & 3 \\ 3 & 0.5 & 1 \end{smallmatrix}\Big)$ and notice that algorithm B would wrongly pick out the job of cost $0.5$, thus forcing another person into a job of cost $3$. But I'd expect these situations to be relatively rare, and indeed the simulations suggest that algorithm B does a better job much more often.
– Jim
Jan 14, 2021 at 11:45
• I agree with you in this. Sure, occasionally A may be better.
– ttnphns
Jan 14, 2021 at 11:58
• Are you interested only in greedy approaches or maybe you are after an optimal approach?
– ttnphns
Jan 14, 2021 at 11:59
• @ttnphns For the sake of the question I'm only interested in the two greedy approaches that I outlined.
– Jim
Jan 14, 2021 at 12:04

In your greedy algorithms you are assigning $$n-1$$ people to jobs by for _ in range(n - 1). Thus you are assigning one job too little - even though this choice is trivial it is missing in your objective. When fixing it to $$n$$ this should solve your problem.