# A combinatorial optimization problem [closed]

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?

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.