research-article

Optimal online assignment with forecasts

Authors:

Erik Vee,

Sergei Vassilvitskii,

Jayavel ShanmugasundaramAuthors Info & Claims

EC '10: Proceedings of the 11th ACM conference on Electronic commerce

Pages 109 - 118

https://doi.org/10.1145/1807342.1807360

Published: 07 June 2010 Publication History

Get Access

Abstract

Motivated by the allocation problem facing publishers in display advertising we formulate the online assignment with forecast problem, a version of the online allocation problem where the algorithm has access to random samples from the future set of arriving vertices. We provide a solution that allows us to serve Internet users in an online manner that is provably nearly optimal. Our technique applies to the forecast version of a large class of online assignment problems, such as online bipartite matching, allocation, and budgeted bidders, in which we wish to minimize the value of some convex objective function subject to a set of linear supply and demand constraints.

Our solution utilizes a particular subspace of the dual space, allowing us to describe the optimal primal solution implicitly in space proportional to the demand side of the input graph. More importantly, it allows us to prove that representing the primal solution using such a compact allocation plan yields a robust online algorithm which makes near-optimal online decisions. Furthermore, unlike the primal solution, we show that the compact allocation plan produced by considering only a sampled version of the original problem generalizes to produce a near optimal solution on the full problem instance.

References

[1]

Moses Charikar, Chandra Chekuri, and Martin Pál. Sampling bounds for stochastic optimization. In Chandra Chekuri, Klaus Jansen, José, D. P. Rolim, and Luca Trevisan, editors, APPROX-RANDOM, volume 3624 of Lecture Notes in Computer Science, pages 257--269. Springer, 2005.

Digital Library

Google Scholar

[2]

Nikhil R. Devenur and Thomas P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In John Chuang, Lance Fortnow, and Pearl Pu, editors, ACM Conference on Electronic Commerce, pages 71--78. ACM, 2009.

Digital Library

Google Scholar

[3]

Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, and S. Muthukrishnan. Online stochastic matching: Beating 1-1/e. 2009.

Google Scholar

[4]

Arpita Ghosh, Preston McAfee, Kishore Papineni, and Sergei Vassilvitskii. Bidding for representative allocations for display advertising. In Stefano Leonardi, editor, WINE, volume 5929 of Lecture Notes in Computer Science, pages 208--219. Springer, 2009.

Digital Library

Google Scholar

[5]

R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. In STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352--358, New York, NY, USA, 1990. ACM.

Digital Library

Google Scholar

[6]

Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. J. ACM, 54(5):22, 2007.

Digital Library

Google Scholar

[7]

David B. Shmoys and Chaitanya Swamy. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM, 53(6):978--1012, 2006.

Digital Library

Google Scholar

[8]

Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaram. Optimal online assignment with forecasts. Yahoo Technical Report 2009-005, 2009.

Google Scholar

Cited By

View all

Wang XGuo YTan BYang THuang DXu LZhou HLi XAngélica LLattanzi SMuñoz Medina AAkoglu LGionis AVassilvitskii S(2024)Follow the LIBRA: Guiding Fair Policy for Unified Impression Allocation via Adversarial RewardingProceedings of the 17th ACM International Conference on Web Search and Data Mining10.1145/3616855.3635756(750-759)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1145/3616855.3635756
Ahani NGölz PProcaccia ATeytelboym ATrapp A(2024)Dynamic Placement in Refugee ResettlementCommunications of the ACM10.1145/361107367:5(99-106)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1145/3611073
Yang RFeng ZPu LYang YLiu CHu Q(2024)Dual-View Stack State Learning Network for Attribute-Based Container Location AssignmentWeb and Big Data10.1007/978-981-97-7235-3_31(467-482)Online publication date: 28-Aug-2024
https://doi.org/10.1007/978-981-97-7235-3_31
Show More Cited By

Index Terms

Optimal online assignment with forecasts

Recommendations

Ad serving using a compact allocation plan
EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

A large fraction of online display advertising is sold via guaranteed contracts: a publisher guarantees to the advertiser a certain number of user visits satisfying the targeting predicates of the contract. The publisher is then tasked with solving the ...
Introduction to display advertising: a half-day tutorial
WSDM '11: Proceedings of the fourth ACM international conference on Web search and data mining

Display advertising is one of the two major advertising channels on the web (in addition to search advertising). Display advertising on the Web is usually done by graphical ads placed on the publishers' Web pages. There is no explicit user query, and ...
Real time bid optimization with smooth budget delivery in online advertising
ADKDD '13: Proceedings of the Seventh International Workshop on Data Mining for Online Advertising

Today, billions of display ad impressions are purchased on a daily basis through a public auction hosted by real time bidding (RTB) exchanges. A decision has to be made for advertisers to submit a bid for each selected RTB ad request in milliseconds. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EC '10: Proceedings of the 11th ACM conference on Electronic commerce

June 2010

400 pages

ISBN:9781605588223

DOI:10.1145/1807342

General Chair:
David C. Parkes
Harvard University, USA
,
Program Chairs:
Chrysanthos Dellarocas
Boston University, USA
,
Moshe Tennenholtz
Technion and Microsoft Israel R&D Center

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '10

Sponsor:

SIGecom

EC '10: ACM Conference on Electronic Commerce

June 7 - 11, 2010

Massachusetts, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
503
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)5

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang XGuo YTan BYang THuang DXu LZhou HLi XAngélica LLattanzi SMuñoz Medina AAkoglu LGionis AVassilvitskii S(2024)Follow the LIBRA: Guiding Fair Policy for Unified Impression Allocation via Adversarial RewardingProceedings of the 17th ACM International Conference on Web Search and Data Mining10.1145/3616855.3635756(750-759)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1145/3616855.3635756
Ahani NGölz PProcaccia ATeytelboym ATrapp A(2024)Dynamic Placement in Refugee ResettlementCommunications of the ACM10.1145/361107367:5(99-106)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1145/3611073
Yang RFeng ZPu LYang YLiu CHu Q(2024)Dual-View Stack State Learning Network for Attribute-Based Container Location AssignmentWeb and Big Data10.1007/978-981-97-7235-3_31(467-482)Online publication date: 28-Aug-2024
https://doi.org/10.1007/978-981-97-7235-3_31
Gao YWei XJing XShi YGao XChen G(2023)Online Shipping Container Pricing Strategy Achieving Vanishing Regret with Limited Inventory2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00392(1719-1731)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00392
Wang XTan BGuo YYang THuang DXu LFreris NZhou HLi XZhang ARangwala H(2022)CONFLUX: A Request-level Fusion Framework for Impression Allocation via Cascade DistillationProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539044(4070-4078)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539044
Cheng XLiu CDai LZhang PFang ZZu ZSelcuk Candan KLiu HAkoglu LLuna Dong XTang J(2022)An Adaptive Unified Allocation Framework for Guaranteed Display AdvertisingProceedings of the Fifteenth ACM International Conference on Web Search and Data Mining10.1145/3488560.3498500(132-140)Online publication date: 11-Feb-2022
https://dl.acm.org/doi/10.1145/3488560.3498500
Wang LHan LChen XLi CHuang JZhang WZhang WHe XLuo D(2022)Hierarchical Multiagent Reinforcement Learning for Allocating Guaranteed Display AdsIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2021.307048433:10(5361-5373)Online publication date: Oct-2022
https://doi.org/10.1109/TNNLS.2021.3070484
Bampis EEscoffier BXefteris M(2022)Canadian Traveller Problem with PredictionsApproximation and Online Algorithms10.1007/978-3-031-18367-6_6(116-133)Online publication date: 21-Oct-2022
https://doi.org/10.1007/978-3-031-18367-6_6
Dinitz MIm SLavastida TMoseley BVassilvitskii SRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Faster matchings via learned dualsProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541056(10393-10406)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3541056
Wu DChen CChen XPan JYang XTan QXu JLee K(2021)Impression Allocation and Policy Search in Display Advertising2021 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM51629.2021.00086(749-756)Online publication date: Dec-2021
https://doi.org/10.1109/ICDM51629.2021.00086
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Ad serving using a compact allocation plan

Introduction to display advertising: a half-day tutorial

Real time bid optimization with smooth budget delivery in online advertising