Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
An improved approximation algorithm for resource allocation
Calinescu G., Chakrabarti A., Karloff H., Rabani Y. ACM Transactions on Algorithms7 (4):1-7,2011.Type:Article
Date Reviewed: Jan 18 2012

The resource allocation problem finds the most profitable subset of tasks for a given limited resource. It is also known as the bandwidth allocation problem, resource constrained scheduling, or call admission control, and is nondeterministic polynomial-time hard (NP-hard). This paper addresses the resource allocation problem, proving that it can be “(1/2 -- ε)-approximated in randomized polynomial time.”

Section 1, the introduction, begins by formulating the problem. After giving an overview of earlier related works, it states the algorithm’s complexity in three theorems. Sections 2 and 3 provide detailed proofs of the theorems. To understand the proofs, a strong background in complexity, optimization, and probability theory is required.

Reviewer:  Maulik A. Dave Review #: CR139783 (1206-0605)
Bookmark and Share
  Featured Reviewer  
 
Sequencing And Scheduling (F.2.2 ... )
 
 
Combinatorial Algorithms (G.2.1 ... )
 
 
Probabilistic Algorithms (Including Monte Carlo) (G.3 ... )
 
 
Combinatorics (G.2.1 )
 
 
Probability And Statistics (G.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Sequencing And Scheduling": Date
Constrained optimum communication trees and sensitivity analysis
Agarwal S., Mittal A., Sharma P. SIAM Journal on Computing 13(2): 315-328, 1984. Type: Article
Feb 1 1985
Scheduling independent 2-processor tasks to minimize schedule length
Blazewicz J., Weglarz J., Drabowski M. Information Processing Letters 18(5): 267-273, 1984. Type: Article
Jan 1 1985
A storage-size selection problem
Friesen D., Langston M. Information Processing Letters 18(5): 295-296, 1984. Type: Article
Feb 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy