(O (N1/2A log(NC) Hybrid Auction Algorithm) This exercise, due to Ahuja and Orlin [1987], shows how the auction algorithm can be combined with a more traditional primal-dual method to obtain an algorithm with an improved running time bound. The auction algorithm is used to assign the first N - O )N1/2 persons and the primal-dual method is used to assign the rest. Consider the solution of the assignment problem by the Gauss-Seidel variant of the scaled auction algorithm ( = 1 throughout).
(b) Suppose that at the outset of each subproblem we use a modified GaussSeidel auction procedure in which only persons i with profit margins πi greater than or equal to π0 i -(6N) 1/2 are allowed to place bids. Show that this procedure can be implemented so that at most (6N) 1/2 + 1 iterations are performed at each person node i, and that it terminates in O(N1/2A) time. Furthermore the number of unassigned persons after termination is at most (6N) 1/2.
(c) Assume that there exists some algorithm X which, given an incomplete assignment S and a price vector p obeying -CS, produces a new pair (S , p ) obeying -CS in O(A) time, with S containing one more assignment than S (Exercise 7.21 indicates how such an algorithm may be constructed). Outline how one would construct an O ( N1/2 A log(NC)) assignment algorithm. 7.2