NDLI: Forward and reverse auction algorithms for Nonlinear Resource Allocation

Content Provider	IEEE Xplore Digital Library
Author	Bangla, A.K. Castanon, D.A.
Copyright Year	2013
Description	Author affiliation: Boston Univ., Boston, MA, USA (Bangla, A.K.; Castanon, D.A.)
Abstract	We study the problem of optimally assigning N divisible resources to M competing tasks, where the performance cost of each task is a convex function of the resources allocated. This is called the Nonlinear Resource Allocation Problem (RAP). This class of problems arises in diverse fields such as search theory, statistics, finance, economics, logistics, sensor and wireless networks. In our recent work, we proposed a class of algorithms, RAP Auction, which were based on extensions of Auction algorithms for linear assignment problems. RAP Auction was shown to find a near optimal solution in finite time and converge under asynchronous computation. However, major limitations of RAP auction were the lack of stronger complexity results and mediocre empirical performance compared to alternative algorithms. In this paper, we develop a new class of algorithms for the solution RAP problems, based on the use of forward and reverse auction principles, along with scaling techniques. The new algorithms can be shown to have pseudo-polynomial complexity and are significantly faster in standard benchmarks than competing special purpose and general purpose state of the art methods.
Sponsorship	IEEE Control Syst. Soc.
Starting Page	2364
Ending Page	2371
File Size	521161
Page Count	8
File Format	PDF
ISBN	9781467357142
ISSN	07431546
e-ISBN	9781467357173
DOI	10.1109/CDC.2013.6760234
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-12-10
Publisher Place	Italy
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Resource management Complexity theory Cost function Convex functions Vectors Search problems Standards
Content Type	Text
Resource Type	Article
Subject	Control and Optimization Control and Systems Engineering Modeling and Simulation

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Asynchronous auction for distributed nonlinear Resource Allocation

Auction algorithm for Nonlinear Resource Allocation Problems

Pseudo-polynomial auction algorithm for Nonlinear Resource Allocation

Accelerated dual coordinate algorithms for separable convex cost network flow problems

A random coordinate descent method for large-scale resource allocation problems

Link resource allocation for maximizing the rigidity of multi-agent formations

Greedy sensor selection: Leveraging submodularity

The convergence rate of Newton-Raphson consensus optimization for quadratic cost functions

Optimal leader allocation in UAV formation pairs under costly switching

Forward and reverse auction algorithms for Nonlinear Resource Allocation

Similar Documents

Asynchronous auction for distributed nonlinear Resource Allocation

Auction algorithm for Nonlinear Resource Allocation Problems

Pseudo-polynomial auction algorithm for Nonlinear Resource Allocation

Accelerated dual coordinate algorithms for separable convex cost network flow problems

A random coordinate descent method for large-scale resource allocation problems

Link resource allocation for maximizing the rigidity of multi-agent formations

Greedy sensor selection: Leveraging submodularity

The convergence rate of Newton-Raphson consensus optimization for quadratic cost functions

Optimal leader allocation in UAV formation pairs under costly switching

Forward and reverse auction algorithms for Nonlinear Resource Allocation