Near Optimal Online Algorithms and Fast ApproximationAlgorithms for Resource Allocation Problems∗Nikhil R. DevanurMicrosoft ResearchRedmond, WA, [email protected] JainMicrosoft ResearchRedmond, WA, [email protected] Sivan†Computer Sciences Dept.,Univ. of Wisconsin-MadisonMadison, WI, [email protected] A. Wilkens‡Computer Science Division,Univ. of California at BerkeleyBerkeley, CA, [email protected] present algorithms for a class of resource allocation problemsboth in the online setting with stochastic input and in the offlinesetting. This class of problems contains many i nteresti ng specialcases such as the Adwords problem. In the online setting we in-troduce a new distributional model call ed the adversarial stochasticinput model, which is a generalization of the i.i.d model with un-known distributions, where the distributions can change over time.In t his model we give a 1 − O(ǫ) approximation algorithm for theresource allocation problem, with almost the weakest possible as-sumption: the ratio of the maximum amount of resource consumedby any single request to the total capacity of the resource, and theratio of the profit contributed by any single request to the optimalprofit is at mostǫ2/ log(1/ǫ)2log n+log(1/ǫ)where n is the number of resourcesavailable. There are i nstances where this ratio is ǫ2/ log n such thatno randomized algorithm can have a competitive ratio of 1 − o(ǫ)even in the i.i.d model. The upper bound on ratio that we requireimproves on the previous upper-bound for the i.i.d case by a factorof n.Our proof technique also gives a very simple proof that the greedyalgorithm has a competitive ratio of 1 − 1/e for the Adwords prob-lem in the i.i.d model with unknown distributions, and more gen-erally in the adversarial stochastic input model, when there is nobound on the bid to budget rati o. All the previous proofs assume∗A full version of this paper, w ith all the proofs, is available athttp://arxiv.org†Part of this work was done while the author was at Microsoft Re-search, Redmond‡Part of this work was done while the author was at Microsoft Re-search, RedmondPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.EC’11, June 5–9, 2011, San Jose, California, USA.Copyright 2011 ACM 978-1-4503-0261-6/11/06 ...$10.00.that either bids are very small compared to budgets or somethingvery similar to this.In t he offline setting we give a fast algorithm to solve very largeLPs with both packing and covering constraints. We give algo-rithms to approximately solve (within a factor of 1 + ǫ) the mixedpacking-covering problem wit h O(γm log nǫ2) oracle calls where theconstraint matrix of this LP has dimension n × m, and γ is a pa-rameter which is very si mi lar to the ratio described for the onlinesetting.We discuss several applications, and how our algorithms improveexisting results in some of these applications.Categories and Subject DescriptorsF.2.0 [Analysis of Algorithms and Problem Complexity]: Gen-eral; J.4 [Social and Behavioral Sciences]: EconomicsGeneral TermsAlgorithms, Economics, TheoryKeywordsOnline algorithms, St ochastic input, Packing-Covering1. INTRODUCTIONThe results in this paper fall into distinct categories of compet-itive algorithms for online problems and fast approximation algo-rithms for offline problems. We have two main results in the onlineframework and one result in the offline setting. However they allshare common techniques.There has been an increasing interest in online algorithms moti-vated by applications to online advertising. The most well knownis the Adwords problem introduced by Mehta et. al. [MSVV05],where the algorithm needs to assign keywords arriving online tobidders to maximize profit, subject to budget constraints for thebidders. The problem has been analyzed in the traditional frame-work for online algorithms: worst-case competitive analysis. Aswith many online problems, the worst-case competitive analysis isnot entirely satisfactory and there has been a drive in the last fewyears to go beyond the worst-case analysis. The predominant ap-proach has been to assume that the input satisfies some stochasticproperty. For instance the random permutation model (introduced29by Goel and Mehta [GM08]) assumes t hat the adversary picks theset of keywords, but the order in which the keywords arrive is cho-sen uniformly at random. A closely related model is the i.i.d model:assume that the keywords are i.i.d samples from a fixed distribution,which is unknown to the algorithm. Stronger assumptions such asi.i.d samples from a known distri bution have also been considered.First Result.A key parameter on which many of the algorithms for Adwordsdepend is the bid to budget ratio. For instance in Mehta et. al.[MSVV05] and Buchbinder, Jain and Naor [BJN07] the algorithmachieves a worst case competitive ratio that tends to 1 − 1/e as thebid to budget ratio (let’s call it γ) tends to 0. (1 − 1/e is also thebest competitive ratio that any randomized algorithm can achievein the worst case.) Devanur and Hayes [DH09] showed that in therandom permutation model, the competitive ratio tends t o 1 as γtends to 0. This result showed that competitive ratio of algorithmsin stochastic models could be much better than that of algorithmsin the worst case. The important question since then has been todetermine the optimal trade-off between γ and the competitive ra-tio. [DH09] showed how to get a 1- O(ǫ) competitive ratio when γis at mostǫ3n log(mn/ǫ)where n is the number of advertisers and mis the number of keywords. Subsequently Agrawal, Wang and Ye[AWY09] improved the bound on γ toǫ2n log(mn/ǫ). The papers ofFeldman et. al. [FHK+10] and Agrawal, Wang and Ye [AWY09]have al so shown that the technique of [DH09] can be extended toother online problems.The first main result i n this paper is the following 3-fold improve-ment of previous results: (Theorems 2 - 4)1. We give an algorithm which improves the bound on γ toǫ2/ log(1/ǫ)2log(n)+log(1/ǫ). This is almost optimal; we show a lowerbound ofǫ2log(n).2. The