Budgeted Allocations in the Full-Information Setting
| Title | Budgeted Allocations in the Full-Information Setting |
| Publication Type | Book Chapters |
| Year of Publication | 2008 |
| Authors | Srinivasan A |
| Editor | Goel A, Jansen K, Rolim J, Rubinfeld R |
| Book Title | Approximation, Randomization and Combinatorial Optimization. Algorithms and TechniquesApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques |
| Series Title | Lecture Notes in Computer Science |
| Volume | 5171 |
| Pagination | 247 - 253 |
| Publisher | Springer Berlin / Heidelberg |
| ISBN Number | 978-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. |
| URL | http://dx.doi.org/10.1007/978-3-540-85363-3_20 |