# reduction to np hard ordering problem

I am trying to show a reduction from a problem of ordering problem to an np-hard problem that has approximation poly-time algorithm. My problem is: I have M auctions and in each auction I have N bidders. A bidder can bid in all the auctions until he wins one, but if he won one of the auctions he can't win other items. assuming that the auctioneer that plans the auctions has information about all the values that the bidders are willing to bid on all the items before the auctions, he needs to find an ordering that maximizes his profit - meaning the sum he get from all the auctions.

I tried finding an NP-hard problem that I can reduct this problem to, but with no succes.

I thought about max-weighted-IS problem by setting the vertices as : Xij - the value that bidder i is willing to bid on item j, and then add edges between all the vertices that have the same j-th value and between all the vertices that have the same i-th value, thus promising that the vertices in the independent set will have preserve the constraing of the auctio, but the problem in this reduction is that given an max weighted indepndent set the max ordering is not necceserily optimal.

Any help would be appriciated.

Thanks

• Do you have a reason to believe that your problem could be reduced to a particular kind of known problem? If you have any ideas, sharing them may improve the answers you get here. Commented Aug 23, 2014 at 17:04
• You are right, I edited the question and added my idea of finding a reduction to max-weighted IS problem
– jhon
Commented Aug 23, 2014 at 17:15
• I'm puzzled: What do you mean by "the sum he gets from all the auctions"? In an auction, a non-winning bid isn't lost, so you're looking at value minus bid for the only item 'he' won, or zero if 'he' hasn't won any bids. Right? Are the actual values given as input to the problem? Commented Aug 25, 2014 at 0:08

I think this can be solved in polynomial time since it is essentially asking for a maximum weight matching in a bipartite graph. Take the complete bipartite graph $K_{N,M}$ where the color classes are the bidders and the items, respectively. Now let $X$ be a maximum weight matching with respect to the weight function $w(i,j)=$value that bidder $i$ is willing to bid on item $j$. I assume $w(i,j)\neq w(i',j)$ for $i\neq i'$.
Clearly, $w(X)$ is an upper bound for the profit of the auctioneer. But this bound can always be achieved: Pick an edge $(i,j)\in X$ such that $w(i,j)> w(i',j)$ for all $i'\neq i$ (such an edge always exists), sell item $j$ in the first auction (to bidder $i$), remove bidder $i$ and item $j$, and continue with the smaller problem.