Approximation algorithms for the max-min allocation problem

Subhash Khot, Ashok Kumar Ponnuswami

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings
PublisherSpringer Verlag
Pages204-217
Number of pages14
ISBN (Print)9783540742074
DOIs
StatePublished - 2007
Event10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007 - Princeton, NJ, United States
Duration: Aug 20 2007Aug 22 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4627 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007
CountryUnited States
CityPrinceton, NJ
Period8/20/078/22/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximation algorithms for the max-min allocation problem'. Together they form a unique fingerprint.

  • Cite this

    Khot, S., & Ponnuswami, A. K. (2007). Approximation algorithms for the max-min allocation problem. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings (pp. 204-217). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4627 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-74208-1_15