Approximation algorithms for dynamic resource allocation

被引：7

作者：

Farias, VF

Van Roy, B ^{[1
]}

机构：

[1] Terman Engn Ctr 427, Dept Management Sci & Engn, Stanford, CA 94305 USA

[2] Stanford Univ, Stanford, CA 94305 USA

来源：

OPERATIONS RESEARCH LETTERS | 2006年 / 34卷 / 02期

基金：

美国国家科学基金会;

关键词：

resource allocation; scheduling; approximation algorithms; project management; randomized rounding;

D O I：

10.1016/j.orl.2005.02.006

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, generates utility, and determines the subsequent state of the activity. We study the complexity of, and approximation algorithms for, maximizing average utility. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：180 / 190

页数：11

共 8 条

[1] On multidimensional packing problems [J].