4
$\begingroup$

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.

Simulating algorithms A and B.

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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – ttnphns Jan 14 at 11:37
  • $\begingroup$ @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. $\endgroup$ – Jim Jan 14 at 11:45
  • $\begingroup$ I agree with you in this. Sure, occasionally A may be better. $\endgroup$ – ttnphns Jan 14 at 11:58
  • $\begingroup$ Are you interested only in greedy approaches or maybe you are after an optimal approach? $\endgroup$ – ttnphns Jan 14 at 11:59
  • $\begingroup$ @ttnphns For the sake of the question I'm only interested in the two greedy approaches that I outlined. $\endgroup$ – Jim Jan 14 at 12:04
2
$\begingroup$

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.

Just because I couldn't resist not mentioning it. There are extremely good polynomial time exact algorithms for the bipartite matching problem you are describing. ;)

$\endgroup$
1
  • $\begingroup$ Fantastic! This fixes it. And yes, I was aware that there's better approaches to the problem. I was going through some notes on probability models and just wanted to sanity check the examples they gave. $\endgroup$ – Jim Jan 17 at 14:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.