Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Approximate Algorithm
Polynomial Time
Resource Allocation
Related Publications
(11)
Multicommodity demand flow in a tree and packing integer programs
A unified approach to approximating resource allocation and scheduling
Approximation Algorithms for the Unsplittable Flow Problem
New approaches to covering and packing problems
The Demand Matching Problem
Subscribe
Academic
Publications
Improved Approximation Algorithms for Resource Allocation
Improved Approximation Algorithms for Resource Allocation,10.1007/3540478671_28,Gruia Calinescu,Amit Chakrabarti,Howard J. Karloff,Yuval Rabani
Edit
Improved Approximation Algorithms for Resource Allocation
(
Citations: 34
)
BibTex

RIS

RefWorks
Download
Gruia Calinescu
,
Amit Chakrabarti
,
Howard J. Karloff
,
Yuval Rabani
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 NPhard
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=4approximation. Wealso give a simpler and faster...
Conference:
Integer Programming and Combinatorial Optimization  IPCO
, pp. 401414, 2002
DOI:
10.1007/3540478671_28
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
Citation Context
(28)
...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. Chakaravarthy
,
et al.
Minimum Cost Resource Allocation for Meeting Job Requirements
...Calinescu et al. [
8
] considered the UBRAP problem and presented a 3approximation 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 3approximation 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. Chakaravarthy
,
et 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 nondecreasing capacity profiles...
Nikhil Bansal
,
et 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 UFPNBA are greedy algorithms [20,22,2] and randomized rounding of the multicommodity flow based LP relaxation [30,7,
9
,12]...
Chandra Chekuri
,
et al.
Unsplittable Flow in Paths and Trees and ColumnRestricted 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 QuasiPTAS...
Julia Chuzhoy
,
et al.
Resource Minimization Job Scheduling
References
(8)
A Faster Strongly Polynomial Minimum Cost Flow Algorithm
(
Citations: 144
)
JAMES B. ORLIN
Journal:
Operations Research
, vol. 41, no. 2, pp. 338350, 1993
Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints
(
Citations: 12
)
Stefano Leonardi
,
Alberto Marchettispaccamela
,
Andrea Vitaletti
Conference:
Foundations of Software Technology and Theoretical Computer Science  FSTTCS
, pp. 409420, 2000
Maximizing the value of a space mission
(
Citations: 31
)
Nicholas G. Hall
,
Michael J. Magazine
Journal:
European Journal of Operational Research  EJOR
, vol. 78, no. 2, pp. 224241, 1994
A unified approach to approximating resource allocation and scheduling
(
Citations: 171
)
Amotz BarNoy
,
Reuven BarYehuda
,
Ari Freund
,
Baruch Schieber
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 735744, 2000
Scheduling jobs with fixed start and end times
(
Citations: 114
)
E. M. Arkin
,
E. B. Silverberg
Journal:
Discrete Applied Mathematics  DAM
, vol. 18, no. 1, pp. 18, 1987
Sort by:
Citations
(34)
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
(
Citations: 1
)
Paul Bonsma
,
Jens Schulz
,
Andreas Wiese
Journal:
Computing Research Repository  CORR
, vol. abs/1102.3, pp. 4756, 2011
Improving LTL truck load utilization on line
Joris van de Klundert
,
Bernhard Otten
Journal:
European Journal of Operational Research  EJOR
, vol. 210, no. 2, pp. 336343, 2011
A Simulated Annealing Algorithm for Resource Allocation and Scheduling with Precedence Constraints in the GLECLUBS/eGLECLUBS Pipelines
Shaoqiang Zhang
,
Huazhi Sun
,
Guojun Li
,
Zhengchang Su
Conference:
IEEE International Conference on Computational Science and Engineering  CSE
, 2011
Minimum Cost Resource Allocation for Meeting Job Requirements
Venkatesan T. Chakaravarthy
,
Gyana R. Parija
,
Sambuddha Roy
,
Yogish Sabharwal
,
Amit Kumar
Published in 2011.
Varying bandwidth resource allocation problem with bag constraints
(
Citations: 3
)
Venkatesan T. Chakaravarthy
,
Vinayaka Pandit
,
Yogish Sabharwal
,
Deva P. Seetharam
Conference:
International Parallel and Distributed Processing Symposium/International Parallel Processing Symposium  IPDPS(IPPS)
, pp. 110, 2010