---
_id: '11797'
abstract:
- lang: eng
  text: "Inspired by online ad allocation, we study online stochastic packing integer
    programs from theoretical and practical standpoints. We first present a near-optimal
    online algorithm for a general class of packing integer programs which model various
    online resource allocation problems including online variants of routing, ad allocations,
    generalized assignment, and combinatorial auctions. As our main theoretical result,
    we prove that a simple dual training-based algorithm achieves a (1 − o(1))-approximation
    guarantee in the random order stochastic model. This is a significant improvement
    over logarithmic or constant-factor approximations for the adversarial variants
    of the same problems (e.g. factor 1−1\U0001D452 for online ad allocation, and
    log(m) for online routing). We then focus on the online display ad allocation
    problem and study the efficiency and fairness of various training-based and online
    allocation algorithms on data sets collected from real-life display ad allocation
    system. Our experimental evaluation confirms the effectiveness of training-based
    algorithms on real data sets, and also indicates an intrinsic trade-off between
    fairness and efficiency."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Jon
  full_name: Feldman, Jon
  last_name: Feldman
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Nitish
  full_name: Korula, Nitish
  last_name: Korula
- first_name: Vahab S.
  full_name: Mirrokni, Vahab S.
  last_name: Mirrokni
- first_name: Cliff
  full_name: Stein, Cliff
  last_name: Stein
citation:
  ama: 'Feldman J, Henzinger MH, Korula N, Mirrokni VS, Stein C. Online stochastic
    packing applied to display ad allocation. In: <i>18th Annual European Symposium
    on Algorithms</i>. Vol 6346. Springer Nature; 2010:182–194. doi:<a href="https://doi.org/10.1007/978-3-642-15775-2_16">10.1007/978-3-642-15775-2_16</a>'
  apa: 'Feldman, J., Henzinger, M. H., Korula, N., Mirrokni, V. S., &#38; Stein, C.
    (2010). Online stochastic packing applied to display ad allocation. In <i>18th
    Annual European Symposium on Algorithms</i> (Vol. 6346, pp. 182–194). Liverpool,
    United Kingdom: Springer Nature. <a href="https://doi.org/10.1007/978-3-642-15775-2_16">https://doi.org/10.1007/978-3-642-15775-2_16</a>'
  chicago: Feldman, Jon, Monika H Henzinger, Nitish Korula, Vahab S. Mirrokni, and
    Cliff Stein. “Online Stochastic Packing Applied to Display Ad Allocation.” In
    <i>18th Annual European Symposium on Algorithms</i>, 6346:182–194. Springer Nature,
    2010. <a href="https://doi.org/10.1007/978-3-642-15775-2_16">https://doi.org/10.1007/978-3-642-15775-2_16</a>.
  ieee: J. Feldman, M. H. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein, “Online
    stochastic packing applied to display ad allocation,” in <i>18th Annual European
    Symposium on Algorithms</i>, Liverpool, United Kingdom, 2010, vol. 6346, pp. 182–194.
  ista: 'Feldman J, Henzinger MH, Korula N, Mirrokni VS, Stein C. 2010. Online stochastic
    packing applied to display ad allocation. 18th Annual European Symposium on Algorithms.
    ESA: European Symposium on Algorithms, LNCS, vol. 6346, 182–194.'
  mla: Feldman, Jon, et al. “Online Stochastic Packing Applied to Display Ad Allocation.”
    <i>18th Annual European Symposium on Algorithms</i>, vol. 6346, Springer Nature,
    2010, pp. 182–194, doi:<a href="https://doi.org/10.1007/978-3-642-15775-2_16">10.1007/978-3-642-15775-2_16</a>.
  short: J. Feldman, M.H. Henzinger, N. Korula, V.S. Mirrokni, C. Stein, in:, 18th
    Annual European Symposium on Algorithms, Springer Nature, 2010, pp. 182–194.
conference:
  end_date: 2010-09-08
  location: Liverpool, United Kingdom
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2010-09-06
date_created: 2022-08-11T12:14:20Z
date_published: 2010-09-01T00:00:00Z
date_updated: 2023-02-13T11:36:46Z
day: '01'
doi: 10.1007/978-3-642-15775-2_16
extern: '1'
external_id:
  arxiv:
  - '1001.5076'
intvolume: '      6346'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1001.5076
month: '09'
oa: 1
oa_version: Preprint
page: 182–194
publication: 18th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '3642157742'
  issn:
  - 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Online stochastic packing applied to display ad allocation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6346
year: '2010'
...