Academic
Publications
Improved Approximation Algorithms for Resource Allocation

Improved Approximation Algorithms for Resource Allocation,10.1007/3-540-47867-1_28,Gruia Calinescu,Amit Chakrabarti,Howard J. Karloff,Yuval Rabani

Improved Approximation Algorithms for Resource Allocation   (Citations: 34)
BibTex | RIS | RefWorks Download
Abstract: We study the problem ofnding a most protable subset of n given tasks, each with a givenstart andnish time as well as prot and resource requirement, that at no time exceeds thequantity B of available resource. We show that this NP-hard Resource Allocation problemcan be (1=2 ")-approximated in polynomial time, which improves upon earlier approximationresults for this problem, the best previously published result being a 1=4-approximation. Wealso give a simpler and faster...
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Nevertheless, constant factor approximation algorithms have been obtained under the socalled No Bottleneck Assumptions (NBA) (see [CCKR02], [CMS07], [CCS10]) wherein it is assumed that the demand of any job is no more than the bandwidth available at any point...

    Venkatesan T. Chakaravarthyet al. Minimum Cost Resource Allocation for Meeting Job Requirements

    • ...Calinescu et al. [8] considered the UBRAP problem and presented a 3-approximation algorithm, based on LProunding technique...
    • ...Our algorithm and analysis for the BAGVBRAP problem builds on the work of Calinescu et al. [8]...
    • ...Calinescu et al. [8] consider the UBRAP problem and present a 3-approximation algorithm...
    • ...The main crux of our work lies in carefully incorporating the implications of the bag constraints and varying bandwidth within the above framework of Calinescu et al. [8]; this requires introducing additional arguments...
    • ...Our algorithm follows the general framework introduced by Calinescu et al. [8]...
    • ...We adapt the LIST algorithm and the analysis of Calinescu et al.[8]...

    Venkatesan T. Chakaravarthyet al. Varying bandwidth resource allocation problem with bag constraints

    • ...The approximation ratio was later improved in a series of papers [5, 7] to (2 +� )...
    • ...We show that if all the tasks are slack and intersecting, then there is a randomized rounding based O(1)-approximation, building on the ideas of Calinescu et al. [7]...
    • ...Our algorithm is an adaptation of the randomized rounding algorithm of Calinescu et al. [7]...
    • ...2The original argument of [7] holds only for non-decreasing capacity profiles...

    Nikhil Bansalet al. A logarithmic approximation for unsplittable flow on line graphs

    • ...See [5,6, 9,12,4,3] for previous work related to UFP on a path...
    • ...Two approximation techniques for UFP-NBA are greedy algorithms [20,22,2] and randomized rounding of the multi-commodity flow based LP relaxation [30,7,9,12]...

    Chandra Chekuriet al. Unsplittable Flow in Paths and Trees and Column-Restricted Packing Int...

    • ...For the special case of Resource Allocation where each job has exactly one time interval (i.e., jI(j)j = 1 for all j), Calinescu et. al. [4] show a factor (2 + )-approximation for any , and Bansal et. al. [1] give a Quasi-PTAS...

    Julia Chuzhoyet al. Resource Minimization Job Scheduling

Sort by: