1
$\begingroup$

A seller wants to sell $N$ goods to $M$ buyers. To that end, the seller collects the prices offered by each buyer $m$ on each good $i$ ($m=1,\cdots,M$, $i=1,\cdots,N$) $p_{mi}$. Given $\{p_{mi}\}$, I am looking for an efficient algorithm for the seller to sell the goods to buyers so as to maximise his profit, under the constraint that each buyer can only buy one good and each good can be sold to only one buyer.

The problem seems to be a combinatorial optimization problem. Is there any polynomial-time algorithm with constant-factor approximation ratio?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Consider the bipartite graph whose left vertices are goods and right vertices are buyers. Draw an edge between each good $i$ and buyer $m$ with weight $p_{mi}$. Now, you want to find a max-weight bipartite matching, for which polynomial-time algorithms exist.

Improve this answer
$\endgroup$
2
$\begingroup$

The "Hungarian method" is a well known technique for solving such problems. Google throws up many hits. An optimal solution can be found in time O(n^3). References etc. can be found on wikipedia.

https://en.wikipedia.org/wiki/Hungarian_algorithm

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .