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.