0

Assume I want to move n goods to n warehouses. I have a n x n cost matrix M, where Mij denotes the cost of transporting jth good to the warehouse. How do I find the transporting plan that minimizes the total costs?

I know there are many general optimal transform algorithms but is there any efficient algorithm tailored for this 1D situation?

Alex Fu
  • 113
  • 1
  • 8
  • Are there any other requirements or conditions aside from what's stated? Otherwise, why would you not simply choose the cheapest warehouse for each good? Is it the case that each warehouse can only receive one good? – mhum Apr 04 '23 at 03:20
  • 1
    O(n^3) algorithm: https://en.wikipedia.org/wiki/Hungarian_algorithm – Aleksei Shestakov Apr 04 '23 at 14:26
  • @mhum Yes, each warehouse can only receive one good. Also, the number of goods is the same as the number of warehouses. So one warehouse's choice would affect all the other warehouses cause they won't be able to choose that good. – Alex Fu Apr 05 '23 at 20:41
  • In that case, this is more readily modelled as an instance of maximum (bipartite) matching: https://en.wikipedia.org/wiki/Maximum_weight_matching rather than as an optimal transport problem – mhum Apr 06 '23 at 20:45
  • How is this 1D if you have an nxn matrix? – Reinderien Apr 06 '23 at 22:15

1 Answers1

0

Found the solution as Hungarian algorithm.

Alex Fu
  • 113
  • 1
  • 8