Title :
Auction algorithm for Nonlinear Resource Allocation Problems
Author :
Bangla, Ajay Kumar ; Castañón, David A.
Author_Institution :
Dept of Electr. & Comput. Eng., Boston Univ., Boston, MA, USA
Abstract :
We study the problem of optimally assigning N divisible resources to M competing missions/tasks. We call this the Nonlinear Resource Allocation Problem (RAP). This simple yet powerful framework has found applications in diverse fields such as search theory, statistics, finance, economics, logistics, sensor and wireless networks. RAP is an instance of convex program but it has a bipartite structure like the assignment/transportation problem. In this paper, we propose a new algorithm, RAP Auction, for this problem which finds a near optimal solution in finite time. Unlike most existing methods in literature, we do not presuppose a particular cost function or assume differentiability or strict convexity. RAP Auction works for any monotonic convex cost function. It has a very simple computation structure amenable to distributed implementation.
Keywords :
resource allocation; search problems; auction algorithm; bipartite structure; economics; finance; logistics; monotonic convex cost function; nonlinear resource allocation problems; search theory; sensor networks; statistics; wireless networks; Bipartite graph; Cost function; MATLAB; Polynomials; Resource management; Search problems; Transportation;
Conference_Titel :
Decision and Control (CDC), 2010 49th IEEE Conference on
Conference_Location :
Atlanta, GA
Print_ISBN :
978-1-4244-7745-6
DOI :
10.1109/CDC.2010.5717911