Bera, Suman Kalyan ; Das, Syamantak ; Kumar, Amit (2014) Minimizing Average Flow-Time under Knapsack Constraint Lecture Notes in Computer Science, 8591 . pp. 584-595. ISSN 0302-9743
Full text not available from this repository.
Official URL: http://doi.org/10.1007/978-3-319-08783-2_50
Related URL: http://dx.doi.org/10.1007/978-3-319-08783-2_50
Abstract
We give the first logarithmic approximation for minimizing average flow-time of jobs in the subset parallel machine setting (also called the restricted assignment setting) under a single knapsack constraint. In a knapsack constraint setting, each job has a profit, and the set of jobs which get scheduled must have a total profit of at least a quantity Π. Our result extends the work of Gupta, Krishnaswamy, Kumar and Segev (APPROX 2009) who considered the special case where the profit of each job is unity. Our algorithm is based on rounding a natural LP relaxation for this problem. In fact, we show that one can use techniques based on iterative rounding.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag. |
| ID Code: | 123520 |
| Deposited On: | 29 Sep 2021 11:15 |
| Last Modified: | 29 Sep 2021 11:15 |
Repository Staff Only: item control page
