The problem of online matching with stochastic rewards is a variant of the online bipartite matching problem where each edge has a probability of "success". When a match is made it succeeds with the probability of the corresponding edge. Introducing this model, Mehta and Panigrahi (FOCS 2012) focused on the special case of identical and vanishingly small edge probabilities and gave an online algorithm which is 0.567 competitive against a deterministic offline LP. For the case of vanishingly small but heterogeneous probabilities (SODA 2015), gave a 0.534 competitive algorithm against the same LP benchmark. We study a generalization of the problem to vertex-weighted graphs and compare against clairvoyant algorithms that know the sequence of arrivals and the edge probabilities in advance, but not the outcomes of potential matches. To the best of our knowledge, no results beating @math were previously known for this setting, even for identical probabilities. By introducing a novel path-based formulation, we show that a natural variant of the RANKING algorithm achieves the best possible competitive ratio of @math , for heterogeneous but vanishingly small edge probabilities. Our result also holds for non-vanishing probabilities that decompose as a product of two factors, one corresponding to each vertex of the edge. The idea of a path-based program may be of independent interest in other online matching problems with a stochastic component.
@cite_6 introduced the online bipartite matching model and proposed the optimal @math competitive RANKING algorithm. Birnbaum and Mathieu @cite_20 , Goel and Mehta @cite_7 considerably simplified the original analysis. Subsequently, @cite_18 gave an elegant randomized primal-dual interpretation that we also use here. Their framework applies to and simplifies more general settings, such as vertex-weighted matchings in @cite_0 , and the related budgeted setting (AdWords problem of @cite_2 ). There has also been a series of results in the random arrival model, where there is distributional information in the arrivals that can be exploited for better results @cite_11 @cite_15 @cite_1 @cite_4 @cite_12 . For a detailed survey we refer the reader to the monograph by Mehta @cite_14 .
@cite_18 @cite_14 @cite_4 @cite_7 @cite_1 @cite_6 @cite_0 @cite_2 @cite_15 @cite_12 @cite_20 @cite_11
2401584318 2183531780 2104224720 2011730242 2571343094 2162656786 1522394790 1769120835 2170675255 2048837158 2963337212
We give a simple proof that the ranking algorithm of Karp, Vazirani and Vazirani [KVV90] is 1-1 e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation. The approach also generalizes easily to the vertex-weighted version considered by [AGKM11]. Further we show that the proof is very similar to the deterministic primal-dual argument for the online budgeted allocation problem with small bids (also called the AdWords problem) of [MSVV05]. Matching is a classic problem with a rich history and a significant impact, both on the theory of algorithms and in practice. Recently there has been a surge of interest in the online version of matching and its generalizations, due to the important new application domain of Internet advertising. The theory of online matching and allocation has played a critical role in designing algorithms for ad allocation. This monograph surveys the key problems, models and algorithms from online matchings, as well as their implication in the practice of ad allocation. The goal is to provide a classification of the problems in this area, an introduction into the techniques used, a glimpse into the practical impact, and to provide direction in terms of open questions. Matching continues to find core applications in diverse domains, and the advent of massive online and streaming data emphasizes the future applicability of the algorithms and techniques surveyed here. We consider the online bipartite matching problem in the unknown distribution input model. We show that the Ranking algorithm of [KVV90] achieves a competitive ratio of at least 0.653. This is the first analysis to show an algorithm which breaks the natural 1 - 1 e -barrier' in the unknown distribution model (our analysis in fact works in the stricter, random order model) and answers an open question in [GM08]. We also describe a family of graphs on which Ranking does no better than 0.727 in the random order model. Finally, we show that for graphs which have k > 1 disjoint perfect matchings, Ranking achieves a competitive ratio of at least 1 - √(1 k - 1 k2 + 1 n) -- in particular Ranking achieves a factor of 1 - o(1) for graphs with ω(1) disjoint perfect matchings. We study an online assignment problem, motivated by Adwords Allocation, in which queries are to be assigned to bidders with budget constraints. We analyze the performance of the Greedy algorithm (which assigns each query to the highest bidder) in a randomized input model with queries arriving in a random permutation. Our main result is a tight analysis of Greedy in this model showing that it has a competitive ratio of 1 - 1 e for maximizing the value of the assignment. We also consider the more standard i.i.d. model of input, and show that our analysis holds there as well. This is to be contrasted with the worst case analysis of [MSVV05] which shows that Greedy has a ratio of 1 2, and that the optimal algorithm presented there has a ratio of 1 - 1 e. The analysis of Greedy is important in the Adwords setting because it is the natural allocation algorithm for an auction-style process. From a theoretical perspective, our result simplifies and generalizes the classic algorithm of Karp, Vazirani and Vazirani for online bipartite matching. Our results include a new proof to show that the Ranking alforithm of [KVV90] has a ratio of 1 - 1 e in the worst case. It has been recently discovered [KV07] (independent of our results) that one of the crucial lemmas in [KVV90], related to a certain reduction, is incorrect. Our proof is direct, in that it does not go via such a reduction, which also enables us to generalize the analysis to our online assignment problem. We consider the online stochastic matching problem proposed by [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1 e. Annual IEEE Sympos. Foundations Comput. Sci. 117--126] as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins, and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribution and it needs to be matched upon its arrival to an empty bin. The goal is to maximize the number of allocations. We present an online algorithm for this problem with a competitive ratio of 0.702. Before our result, algorithms with a competitive ratio better than 1-1 e were known under the assumption that the expected number of arriving balls of each type is integral. A key idea of the algorithm is to collect statistics about the decisions of the optimum offline solution using Monte Carlo sampling and use those statistics to guide the decisions of the online algorithm. We also show that our algorithm achieves a competitive ratio of 0.705 when the rates are integral. On the hardness side, we prove that no online algorithm can have a competitive ratio better than 0.823 under the known distribution model (and henceforth under the permutation model). This improves upon the 5 6 hardness result proved by Goel and Mehta [Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. ACM-SIAM Symposium Discrete Algorithms 982--991] for the permutation model. There has been a great deal of interest recently in the relative power of on-line and off-line algorithms. An on-line algorithm receives a sequence of requests and must respond to each request as soon as it is receiveD. An off-line algorithm may wait until all requests have been received before determining its responses. One approach to evaluating an on-line algorithm is to compare its performance with that of the best possible off-line algorithm for the same problem. Thus, given a measure of "profit", the performance of an on-line algorithm can be measured by the worst-case ratio of its profit to that of the optimal off-line algorithm. This general approach has been applied in a number of contexts, including data structures [SITa], bin packing [CoGaJo], graph coloring [GyLe] and the k-server problem [MaMcSI]. Here we apply it to bipartite matching and show that a simple randomized on-line algorithm achieves the best possible performance. We study the following vertex-weighted online bipartite matching problem: G(U, V, E) is a bipartite graph. The vertices in U have weights and are known ahead of time, while the vertices in V arrive online in an arbitrary order and have to be matched upon arrival. The goal is to maximize the sum of weights of the matched vertices in U. When all the weights are equal, this reduces to the classic online bipartite matching problem for which Karp, Vazirani and Vazirani gave an optimal (1−1 e)-competitive algorithm in their seminal work [10]. Our main result is an optimal (1−1 e)-competitive randomized algorithm for general vertex weights. We use random perturbations of weights by appropriately chosen multiplicative factors. Our solution constitutes the first known generalization of the algorithm in [10] in this model and provides new insights into the role of randomization in online allocation problems. It also effectively solves the problem of online budgeted allocations [14] in the case when an agent makes the same bid for any desired item, even if the bid is comparable to his budget - complementing the results of [14, 3] which apply when the bids are much smaller than the budgets. How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a tradeoff revealing LP and use it to derive two optimal algorithms achieving competitive ratios of 1-1 e for this problem. We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of @math , a very familiar bound that holds for many online problems; further, the bound is tight in this case. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the @math bound.Our main result is a @math -approximation online algorithm for stochastic bipartite matching, breaking this @math barrier. Furthermore, we show that no online algorithm can produce a @math approximation for an arbitrarily small @math for this problem. Our algorithms are based on computing an optimal offline solution to the expected instance, and using this solution as a guideline in the process of online allocation. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-) matchings. In addition to guiding the online decision making, these two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution. At the end, we discuss extensions of our results to more general bipartite allocations that are important in a display ad application. We examine the classic on-line bipartite matching problem studied by Karp, Vazirani, and Vazirani [8] and provide a simple proof of their result that the Ranking algorithm for this problem achieves a competitive ratio of 1 -- 1 e. Online matching has received significant attention over the last 15 years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 - 1 epsilon) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the "known I.I.D. model" where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including: (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to [Haeupler, Mirrokni and Zadimoghaddam WINE 2011] to 0.705; and (b) the vertex-weighted case, where we improve the 0.7250 ratio of [Jaillet and Lu Math. Oper. Res 2013] to 0.7299. We also consider two extensions, one is "known I.I.D." with non-integral arrival rate and stochastic rewards; the other is "known I.I.D." b-matching with non-integral arrival rate and stochastic rewards. We present a simple non-adaptive algorithm which works well simultaneously on the two extensions. One of the key ingredients of our improvement is the following (offline) approach to bipartite-matching polytopes with additional constraints. We first add several valid constraints in order to get a good fractional solution f; however, these give us less control over the structure of f. We next remove all these additional constraints and randomly move from f to a feasible point on the matching polytope with all coordinates being from the set 0, 1 k, 2 k,..., 1 for a chosen integer k. The structure of this solution is inspired by [Jaillet and Lu Math. Oper. Res 2013] and is a tractable structure for algorithm design and analysis. The appropriate random move preserves many of the removed constraints (approximately [exactly] with high probability [in expectation]). This underlies some of our improvements, and, we hope, could be of independent interest.