Optimal online assignment with forecasts

Published 7 June 2010

Erik Vee, Sergei Vassilvitskii, Jayavel Shanmugasundaram

Citations95

TL;DR

The online assignment with forecast problem is formulated, a version of the online allocation problem where the algorithm has access to random samples from the future set of arriving vertices, and it is proved that representing the primal solution using such a compact allocation plan yields a robust online algorithm which makes near-optimal online decisions.

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.

Keywords

Computer ScienceDecision Sciences

An optimal algorithm for on-line bipartite matching

701 Citations1990Richard M. Karp, Umesh Vazirani +1 more

This work applies the general approach to data structures, bin packing, graph coloring, and graph coloring to bipartite matching and shows that a simple randomized on-line algorithm achieves the best possible performance.

View PDF

Journal of the ACMAdWords and generalized online matching

622 Citations2007Aranyak Mehta, Amin Saberi +2 more

The notion of a tradeoff revealing LP is introduced and used to derive two optimal algorithms achieving competitive ratios of 1-1/e for this problem of online bipartite matching.

The adwords problem

330 Citations2009Nikhil R. Devanur, Thomas P. Hayes

The problem of a search engine trying to assign a sequence of search keywords to a set of competing bidders, each with a daily spending limit, is considered, and the current literature on this problem is extended by considering the setting where the keywords arrive in a random order.

Online Stochastic Matching: Beating 1-1/e

273 Citations2009Jon Feldman, Aranyak Mehta +2 more

A novel application of the idea of the power of two choices from load balancing, which compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order to characterize an upper bound for the optimum in any scenario.

Boosted sampling

154 Citations2004Anupam Gupta, Martin Pál +2 more

This framework is used to derive constant factor approximations for stochastic versions of Vertex Cover, Steiner Tree and Uncapacitated Facility Location for arbitrary distributions π in one fell swoop.

Lecture notes in computer scienceBidding for Representative Allocations for Display Advertising

121 Citations2009Arpita Ghosh, Preston McAfee +2 more

This work characterize what allocations can be implemented with randomized bidding, namely those where the desired share obtained at each price is a non-increasing function of price.

Journal of the ACMAn approximation scheme for stochastic linear programming and its application to stochastic integer programs

112 Citations2006David B. Shmoys, Chaitanya Swamy

It is shown that for a broad class of 2-stage linear models with recourse, one can, for any ε > 0, in time polynomial in 1/ε and the size of the input, compute a solution of value within a factor of the optimum, in spite of the fact that exponentially many second-stage scenarios may occur.

ACM SIGACT NewsApproximation algorithms for 2-stage stochastic optimization problems

84 Citations2006Chaitanya Swamy, David B. Shmoys

Stochastic optimization provides a means to handle uncertainty by modeling it by a probability distribution over possible realizations of the actual data, called scenarios, and has its roots in the work of Dantzig and Beale in the 1950s.

Lecture notes in computer scienceSampling Bounds for Stochastic Optimization

77 Citations2005Moses Charikar, Chandra Chekuri +1 more

A different proof is given, based on earlier methods of Kleywegt, Shapiro, Homem-De-Mello, and others, that a polynomial number of samples suffice for the SAA method, which applies to integer programs.

Lecture notes in computer scienceOn Two-Stage Stochastic Minimum Spanning Trees

52 Citations2005Kedar Dhamdhere, R. Ravi +1 more

For the two-stage stochastic optimization formulation with finite scenarios, a simple iterative randomized rounding method on a natural LP formulation of the problem yields a nearly best-possible approximation algorithm.