Let $𝐼$ be the set of customers and let $𝐽_𝑖⊆𝐽$ be the set of items from which customer $𝑖∈𝐼$ wants to buy only one, where $𝐽$ are the items. Denote $𝑤(𝑖,𝑗)≥0$ as the price customer $𝑖$ is willing to pay for item $𝑗$. Assume $|𝐼|=|𝐽|=𝑛.$
The question is to find a polynomial time algorithm which maximizes the total revenue independent of the number of customers that actually get an item.
To do this, I created a bipartite graph $I$ and $J$ with source $s$ and sink $t$.
$$
(s,i), i \in I \\
(j,t), j \in J
$$
with capacity $1$ and cost $0$. The cost function we make
$$
w^*(i, j) = \begin{cases}\frac{1}{w(i,j)} & w(i,j) \neq 0 \\ 0 &otherwise\end{cases}.
$$
where edge $(i,j)$ has capacity 1 if $j \in J_i$.
Now, we solve this problem using a min cost max flow algorithm. However, there can be scenario's where a higher flow is selected with a lower cost (and hence lower revenue) where a lower flow with a higher cost should have been selected.
How do I use the min-cost max flow algorithm to select the highest cost unrelated to the amount of flow?
Best Answer
Make it so that everyone is willing to buy every item (but possibly only willing to pay a price of $0$ for it) and you ensure that the maximum flow is $n$.
Your cost function doesn't order $w(i,j)=0$ correctly, so instead use $w^*(i,j) = -w(i,j)$.
At this point, a min-cost max flow will maximize the total revenue. (Ignore edges with $w(i,j)=0$ in the solution, if you like; it won't change the answer.)
This can also be solved as an assignment problem, of course, but this is the min-cost max-flow approach.