Pseudo-polynomial auction algorithm for Nonlinear Resource Allocation

Author

Bangla, A.K. ; Castanon, D.A.

Author_Institution

Dept. of Electr. & Comput. Eng., Boston Univ., Boston, MA, USA

fYear

2011

fDate

June 29 2011-July 1 2011

Firstpage

3880

Lastpage

3885

Abstract

We study the problem of optimally assigning N divisible resources to M competing tasks. This is called the Nonlinear Resource Allocation Problem (RAP). Recently, we proposed a new algorithm, RAP Auction [1], which finds a near optimal solution in finite time. It works for monotonic convex cost functions and has a simple computation structure. In this paper, we propose an elegant extension which enables RAP Auction to have pseudo-polynomial complexity.

Keywords

computational complexity; convex programming; graph theory; resource allocation; competing tasks; computation structure; monotonic convex cost function; near optimal solution; nonlinear resource allocation problem; optimal divisible resource assignment; pseudopolynomial auction algorithm; pseudopolynomial complexity; Absorption; Complexity theory; Convergence; Convex functions; Cost function; Polynomials; Resource management;

fLanguage

English

Publisher

ieee

Conference_Titel

American Control Conference (ACC), 2011

Conference_Location

San Francisco, CA

ISSN

0743-1619

Print_ISBN

978-1-4577-0080-4

Type

conf

DOI

10.1109/ACC.2011.5991436

Filename

5991436

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2857715