Title: General auction method for real-valued optimal transport,
Abstract: The auction method developed by Bertsekas in the late 1970s is a relaxation
technique for solving integer-valued assignment problems. It resembles a
competitive bidding process, where unsatisfied persons (bidders) attempt to
claim the objects (lots) offering the best value. By transforming
integer-valued transport problems into assignment problems, the auction method
can be extended to compute optimal transport solutions. We propose a more
general auction method that can be applied directly to real-valued transport
problems. We prove termination and provide a priori error bounds for the
general auction method. Our numerical results indicate that the complexity of
the general auction is roughly comparable to that of the original auction
method, when the latter is applicable.