Budgeted Allocations in the Full-Information Setting

TitleBudgeted Allocations in the Full-Information Setting
Publication TypeBook Chapters
Year of Publication2008
AuthorsSrinivasan A
EditorGoel A, Jansen K, Rolim J, Rubinfeld R
Book TitleApproximation, Randomization and Combinatorial Optimization. Algorithms and TechniquesApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Series TitleLecture Notes in Computer Science
Volume5171
Pagination247 - 253
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-85362-6
Abstract

We build on the work of Andelman & Mansour and Azar, Birnbaum, Karlin, Mathieu & Thach Nguyen to show that the full-information (i.e., offline) budgeted-allocation problem can be approximated to within 4/3: we conduct a rounding of the natural LP relaxation, for which our algorithm matches the known lower-bound on the integrality gap.

URLhttp://dx.doi.org/10.1007/978-3-540-85363-3_20