d*****r
发帖数: 57 | 1 N bidders bid on N merchandises. Each bidder provides a bidding price on
every of the N merchandises, P(i,j). How to allocate the merchandises to
each the bidder to maximize the revenue? (Of coz, each merchandise can be
sold to one and only one bidder.)
感觉应该是很基本的问题，可惜本人背景太弱，望不吝赐教，多谢！ | a****9
发帖数: 418 | 2 maximum weighted bipartite matching
【在 d*****r 的大作中提到】
: N bidders bid on N merchandises. Each bidder provides a bidding price on
: every of the N merchandises, P(i,j). How to allocate the merchandises to
: each the bidder to maximize the revenue? (Of coz, each merchandise can be
: sold to one and only one bidder.)
: 感觉应该是很基本的问题，可惜本人背景太弱，望不吝赐教，多谢！
| j****a
发帖数: 1277 | 3 max-flow-min-cut
【在 d*****r 的大作中提到】
: N bidders bid on N merchandises. Each bidder provides a bidding price on
: every of the N merchandises, P(i,j). How to allocate the merchandises to
: each the bidder to maximize the revenue? (Of coz, each merchandise can be
: sold to one and only one bidder.)
: 感觉应该是很基本的问题，可惜本人背景太弱，望不吝赐教，多谢！
| l******e
发帖数: 470 | 4 不好使
【在 j****a 的大作中提到】
: max-flow-min-cut
| b**********g
发帖数: 90 | 5 这个问题问得够刁的,
要是只看你的思路的话,还好.
否则还是很难回答的.
是 maximum weighted matching problem
在 bipartite graph 里稍微要容易点.
http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphs
【在 d*****r 的大作中提到】
: N bidders bid on N merchandises. Each bidder provides a bidding price on
: every of the N merchandises, P(i,j). How to allocate the merchandises to
: each the bidder to maximize the revenue? (Of coz, each merchandise can be
: sold to one and only one bidder.)
: 感觉应该是很基本的问题，可惜本人背景太弱，望不吝赐教，多谢！
| s**9
发帖数: 207 | 6 How about a greedy algorithm? Output the greatest Pij, then delete row i and
column j; repeat for N times.
Proof that Pij is in one optimal solution: suppose there is an optimal
solution that doesn't include Pij. Then in the solution, bidder i is
assigned with an item k where Pik<=Pij. If Pik is replaced with Pij, the
solution is still optimal if Pij=Pik or is better than the original one if
Pij>Pik. Therefore, Pij must be included in a optimal solution.
【在 d*****r 的大作中提到】
: N bidders bid on N merchandises. Each bidder provides a bidding price on
: every of the N merchandises, P(i,j). How to allocate the merchandises to
: each the bidder to maximize the revenue? (Of coz, each merchandise can be
: sold to one and only one bidder.)
: 感觉应该是很基本的问题，可惜本人背景太弱，望不吝赐教，多谢！
| b******t
发帖数: 965 | 7 1 9
9 10
1+10<9+9
and
【在 s**9 的大作中提到】
: How about a greedy algorithm? Output the greatest Pij, then delete row i and
: column j; repeat for N times.
: Proof that Pij is in one optimal solution: suppose there is an optimal
: solution that doesn't include Pij. Then in the solution, bidder i is
: assigned with an item k where Pik<=Pij. If Pik is replaced with Pij, the
: solution is still optimal if Pij=Pik or is better than the original one if
: Pij>Pik. Therefore, Pij must be included in a optimal solution.
|
|
