TY - GEN

T1 - Approximation algorithms for the max-min allocation problem

AU - Khot, Subhash

AU - Ponnuswami, Ashok Kumar

PY - 2007

Y1 - 2007

N2 - 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 (2k - 1)-approximation algorithm for Max-Min when there are k people with subadditive utility functions. We also give a fc/a-approximation algorithm (for α < k/2) if the utility functions are additive and the utility of an item for a person is restricted to 0, 1 or U for some U > 1. The running time of this algorithm depends exponentially on the parameter α. Both the algorithms are combinatorial, simple and easy to analyze.

AB - 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 (2k - 1)-approximation algorithm for Max-Min when there are k people with subadditive utility functions. We also give a fc/a-approximation algorithm (for α < k/2) if the utility functions are additive and the utility of an item for a person is restricted to 0, 1 or U for some U > 1. The running time of this algorithm depends exponentially on the parameter α. Both the algorithms are combinatorial, simple and easy to analyze.

UR - http://www.scopus.com/inward/record.url?scp=38049084076&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38049084076&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-74208-1_15

DO - 10.1007/978-3-540-74208-1_15

M3 - Conference contribution

AN - SCOPUS:38049084076

SN - 9783540742074

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 204

EP - 217

BT - Approximation, Randomization, and Combinatorial Optimization

PB - Springer Verlag

T2 - 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007

Y2 - 20 August 2007 through 22 August 2007

ER -