期刊
INFORMATION PROCESSING LETTERS
卷 100, 期 4, 页码 162-166出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ipl.2006.06.003
关键词
Generalized Assignment Problem; local ratio; approximation algorithms
We present a simple family of algorithms for solving the Generalized Assignment Problem (GAP). Our technique is based on a novel combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for GAP If the approximation ratio of the knapsack algorithm is alpha and its running time is O(f (N)), our algorithm guarantees a (1 + alpha)-approximation ratio, and it runs in O(M . f (N) + M . N), where N is the number of items and M is the number of bins. Not only does our technique comprise a general interesting framework for the GAP problem; it also matches the best combinatorial approximation for this problem, with a much simpler algorithm and a better running time. (c) 2006 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据