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