An approximation algorithm for the general max-min resource sharing problem
成果类型：
Article
署名作者：
Jansen, K
署名单位：
University of Kiel
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-005-0669-1
发表日期：
2006
页码：
547-566
关键词：
摘要：
We propose an approximation algorithm for, the general max-min resource sharing problem with M nonnegative concave constraints on a convex set B. The algorithm is based on a Lagrangian decomposition method and it uses a c-approximation algorithm (called approximate block solver) for a simpler maximization problem over the convex set B. We show that our algorithm achieves within O( M(1nM + is an element of(-2) 1n is an element of(-1))) iterations or calls to the approximate block solver a solution for the general max-min resource sharing problem with approximation ratio c/(1-is an element of). The algorithm is faster and simpler than the previous known approximation algorithms for the problem [ 12, 13].