I am working on a resource allocation problem, which is formulated as an 'assignment problem'. It is solved using Hungarian Method.

Let's assume that below is my assignment problem, where each workers must be assigned specific job which will minimize the overall cost. The cost matrix is given by \begin{bmatrix} Worker/Job & J1 & J2 & J3 \\ W1 &1 & 5 & 3\\W2 & 2 & 4 & 3 \\ W3 &2 & 1 & 8 \end{bmatrix}

Now, using Hungarian algorithm, I could allocate jobs J1--> W1, J2--> W3 and J3-->W2, which minimizes the overall cost.

However, we have assumed that all the processing is done in a centralized location and we know all the costs ($C_{w,j}$) of each jobs assigned to each worker.

I want to know, is there any algorithm which can solve this assignment problem in a distributed manner? For example, each worker knows the cost associated with each job and selects the job which minimizes the cost. However, other worker may select the same jobs.

I understand, they need to convey the information to central entity, but still minimizes the computation in central location by doing local computation. I read about auction algorithm, but need some good resources to read.


Your Answer

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

Browse other questions tagged or ask your own question.