Approximation Algorithms for the Max-Min Allocation Problem
Approximation Algorithms for the Max-Min Allocation Problem
复制标题
最大-最小分配问题的近似算法
DOI：
10.1007/978-3-540-74208-1_15
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Ashok Kumar Ponnuswami
中科院分区：
文献类型：
--
作者：
Subhash Khot;Ashok Kumar Ponnuswami
最高分配问题是向人们分配不可分割的商品，以最大程度地提高人们的最低效用如果实用程序功能是附加功能，并且一个人的实用程序仅限于0、1或u，则给出k/i¾？算法呈指数级取决于参数i¾。这两个算法都是组合，简单易于分析。
The Max-Min allocation problem is to distribute indivisible goods to people so as to maximize the minimum utility of the people. We show a (2ki¾? 1)-approximation algorithm for Max-Min when there are kpeople with subadditive utility functions. We also give a k/i¾?-approximation algorithm (for i¾?≤ k/2) if the utility functions are additive and the utility of an item for a person is restricted to 0, 1 or Ufor some U> 1. The running time of this algorithm depends exponentially on the parameter i¾?. Both the algorithms are combinatorial, simple and easy to analyze.