ABSTRACT
In the Submodular Welfare Maximization (SWM) problem, the input consists of a set of n items, each of which must be allocated to one of m agents. Each agent l has a valuation function vl, where vl(S) denotes the welfare obtained by this agent if she receives the set of items S. The functions vl are all submodular; as is standard, we assume that they are monotone and vl(∅) = 0. The goal is to partition the items into m disjoint subsets S1, S2, ... Sm in order to maximize the social welfare, defined as ∑l = 1m vl(Sl). A simple greedy algorithm gives a 1/2-approximation to SWM in the offline setting, and this was the best known until Vondrak's recent (1-1/e)-approximation algorithm [34]. In this paper, we consider the online version of SWM. Here, items arrive one at a time in an online manner; when an item arrives, the algorithm must make an irrevocable decision about which agent to assign it to before seeing any subsequent items. This problem is motivated by applications to Internet advertising, where user ad impressions must be allocated to advertisers whose value is a submodular function of the set of users / impressions they receive. There are two natural models that differ in the order in which items arrive. In the fully adversarial setting, an adversary can construct an arbitrary / worst-case instance, as well as pick the order in which items arrive in order to minimize the algorithm's performance. In this setting, the 1/2-competitive greedy algorithm is the best possible. To improve on this, one must weaken the adversary slightly: In the random order model, the adversary can construct a worst-case set of items and valuations, but does not control the order in which the items arrive; instead, they are assumed to arrive in a random order. The random order model has been well studied for online SWM and various special cases, but the best known competitive ratio (even for several special cases) is 1/2 + 1/n [9,10], barely better than the ratio for the adversarial order. Obtaining a competitive ratio of 1/2 + Ω(1) for the random order model has been an important open problem for several years. We solve this open problem by demonstrating that the greedy algorithm has a competitive ratio of at least 0.505 for online SWM in the random order model. This is the first result showing a competitive ratio bounded above 1/2 in the random order model, even for special cases such as the weighted matching or budgeted allocation problems (without the so-called 'large capacity' assumptions). For special cases of submodular functions including weighted matching, weighted coverage functions and a broader class of "second-order supermodular" functions, we provide a different analysis that gives a competitive ratio of 0.51. We analyze the greedy algorithm using a factor-revealing linear program, bounding how the assignment of one item can decrease potential welfare from assigning future items. We also formulate a natural conjecture which, if true, would improve the competitive ratio of the greedy algorithm to at least 0.567.
In addition to our new competitive ratios for online SWM, we make two further contributions: First, we define the classes of second-order modular, supermodular, and submodular functions, which are likely to be of independent interest in submodular optimization. Second, we obtain an improved competitive ratio via a technique we refer to as gain linearizing, which may be useful in other contexts (see [26]): Essentially, we linearize the submodular function by dividing the gain of an optimal solution into gain from individual elements, compare the gain when it assigns an element to the optimal solution's gain from the element, and, crucially, bound the extent to which assigning elements can affect the potential gain of other elements.
- Gagan Agarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocation. In SODA. SIAM, 2011. Google ScholarDigital Library
- Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Computing Research Repository, 2009.Google Scholar
- Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. Online prophet-inequality matching with applications to ad allocation. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 18--35. ACM, 2012. Google ScholarDigital Library
- Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA, pages 253--264. Springer, 2007. Google ScholarDigital Library
- Nikhil Devanur and Thomas Hayes. The adwords problem: Online keyword matching with budgeted bidders under random permutations. In EC, pages 71--78, 2009. Google ScholarDigital Library
- Nikhil R. Devanur, Zhiyi Huang, Nitish Korula, Vahab S. Mirrokni, and Qiqi Yan. Whole-page optimization and submodular welfare maximization with online bidders. In ACM Conference on Electronic Commerce, pages 305--322, 2013. Google ScholarDigital Library
- Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In EC, pages 29--38. ACM, 2011. Google ScholarDigital Library
- Nikhil R Devanur, Balasubramanian Sivan, and Yossi Azar. Asymptotically optimal algorithm for stochastic adwords. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 388--404. ACM, 2012. Google ScholarDigital Library
- Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. In STOC, pages 610--618, 2005. Google ScholarDigital Library
- Shahar Dobzinski and Michael Schapira. An improved approximation algorithm for combinatorial auctions with submodular bidders. In SODA, pages 1064--1073, 2006. Google ScholarDigital Library
- J. Feldman, N. Korula, V. Mirrokni, S. Muthukrishnan, and M. Pal. Online ad assignment with free disposal. In WINE, 2009. Google ScholarDigital Library
- Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Cliff Stein. Online stochastic packing applied to display ad allocation. In ESA, pages 182--194. Springer, 2010. Google ScholarDigital Library
- Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S. Muthukrishnan. Online stochastic matching: Beating 1 - 1/e. In FOCS, pages 117--126, 2009. Google ScholarDigital Library
- M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey. An analysis of the approximations for maximizing submodular set functions II. Mathematical Programming Study, 8:73--87, 1978.Google ScholarCross Ref
- Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, pages 982--991, 2008. Google ScholarDigital Library
- B. Haeupler, V. Mirrokni, and M. ZadiMoghaddam. Online stochastic weighted matching: Improved approximation algorithms. In WINE, pages 170--181, 2011. Google ScholarDigital Library
- Bala Kalyanasundaram and Kirk R. Pruhs. An optimal deterministic algorithm for online b -matching. Theoretical Computer Science, 233(1--2):319--325, 2000. Google ScholarDigital Library
- Michael Kapralov, Ian Post, and Jan Vondrák. Online submodular welfare maximization: Greedy is optimal. In SODA, pages 1216--1225, 2013. Google ScholarDigital Library
- Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In STOC, pages 587--596, 2011. Google ScholarDigital Library
- R.M. Karp, U.V. Vazirani, and V.V. Vazirani. An optimal algorithm for online bipartite matching. In STOC, pages 352--358, 1990. Google ScholarDigital Library
- Lehman, Lehman, and N. Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behaviour, pages 270--296, 2006.Google Scholar
- Renato Paes Leme, Vasilis Syrgkanis, and Éva Tardos. Sequential auctions and externalities. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 869--886. SIAM, 2012. Google ScholarDigital Library
- Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: A strongly factor revealing lp approach. In STOC, pages 597--606, 2011. Google ScholarDigital Library
- Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. J. ACM, 54(5):22, 2007. Google ScholarDigital Library
- Vahideh H. Menshadi, Shayan Oveis Gharan, and A. Saberi. Online stochastic matching: Online actions based on offline statistics. In SODA, pages 1285--1294, 2011. Google ScholarDigital Library
- Vahab Mirokni and Morteza Zadimoghaddam. Randomized composable core-sets for distributed submodular maximization. In Proceedings of the 47th Annual Symposium on the Theory of Computing, 2015. To appear. Google ScholarDigital Library
- Vahab S. Mirrokni, Shayan Oveis Gharan, and Morteza ZadiMoghaddam. Simultaneous approximations of stochastic and adversarial budgeted allocation problems. In SODA, pages 1690--1701, 2011. Google ScholarDigital Library
- Vahab S. Mirrokni, Michael Schapira, and Jan Vondrák. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In ACM Conference on Electronic Commerce, pages 70--77, 2008. Google ScholarDigital Library
- Marco Molinaro and R Ravi. The geometry of online packing linear programs. Mathematics of Operations Research, 2013. Google ScholarDigital Library
- G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions. I. Math. Programming, 14(3):265--294, 1978.Google ScholarDigital Library
- Vasilis Syrgkanis and Eva Tardos. Bayesian sequential auctions. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 929--944. ACM, 2012. Google ScholarDigital Library
- Vasilis Syrgkanis and Eva Tardos. Composable and efficient mechanisms. In Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, pages 211--220. ACM, 2013. Google ScholarDigital Library
- Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaram. Optimal online assignment with forecasts. In EC, pages 109--118, 2010. Google ScholarDigital Library
- J. Vondrak. Optimal approximation for the submodular welfare problem in the value oracle model. In STOC, pages 67--74, 2008. Google ScholarDigital Library
Index Terms
- Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
Recommendations
Online Results for Black and White Bin Packing
In online bin packing problems, items of sizes in [0, 1] are to be partitioned into subsets of total size at most 1, called bins. We introduce a new variant where items are of two types, called black and white, and the item types must alternate in each ...
Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing
In this paper, we study 1-space bounded multi-dimensional bin packing and hypercube packing. A sequence of items arrive over time, each item is a d -dimensional hyperbox (in bin packing) or hypercube (in hypercube packing), and the length of each side ...
Tight bounds for online class-constrained packing
Latin American theorotical informaticsWe consider class-constrained packing problems, in which we are given a set of bins, each having a capacity v and c compartments, and n items of M different classes and the same (unit) size. We need to fill the bins with items, subject to capacity ...
Comments