Online budgeted matching in random input models with applications to Adwords

By Gagan Goel, Aranyak Mehta. ACM-SIAM Symposium on Discrete Algorithms, 2008

357 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Online Matching and Ad Allocation (2013, methodology): “The model was introduced in this context by Goel and Mehta [51], who showed that the Greedy algorithm, which matches each incoming vertex to an arbitrary neighbor (breaking ties consistently across different input permutations), achieves a ratio of 1 − (1)e .”
A Dynamic Near-Optimal Algorithm for Online Linear Programming (2009, background): “G T ] 1 6 N ov 2 00”
The adwords problem: online keyword matching with budgeted bidders under random permutations (2009, background): “Apart from 2 A gap in their analysis was discovered by [15], and an alternate proof was given in [10]. the similarity about random ordering of the inputs, the two problems seem to be diﬀerent.”
Online mobile Micro-Task Allocation in spatial crowdsourcing (2016, background): “[32] first proposes the online maximum unweighted bipartite matching problem under the random order model and proves that the competitive ratio of the simple greedy algorithm can be enhanced from 12 under the adversarial model to 1 − 1 e .”
Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs (2011, methodology): “Their result also implies that in the random arrivals model defined by Goel and Mehta [6], where the online nodes arrive in a random order, a simple greedy algorithm achieves a competitive ratio of 1−1/e.”