Consider the auction algorithm applied to assignment problems with benefits in the range [0, C], starting with zero prices.
(a) Show that for dense problems (every person can bid for every object) an object can receive a bid in at most 1 + C/ iterations.
(b) Use the example of Fig. 7.17 (due to D. Castanon) to show that, in general, some objects may receive a bid in a number of iterations that is proportional to nC/.