Document Open Access Logo

The Adwords Problem with Strict Capacity Constraints

Authors Umang Bhaskar, Ajil Jalal, Rahul Vaze

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.30.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Umang Bhaskar
Ajil Jalal
Rahul Vaze

Cite As Get BibTex

Umang Bhaskar, Ajil Jalal, and Rahul Vaze. The Adwords Problem with Strict Capacity Constraints. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.30

Abstract

We study an online assignment problem where the offline servers have capacities, and the objective is to obtain a maximum-weight assignment of requests that arrive online. The weight of edges incident to any server can be at most the server capacity. Our problem is related to the adwords problem, where the assignment to a server is allowed to exceed its capacity. In many applications, however, server capacities are strict and partially-served requests are of no use, motivating the problem we study. 

While no deterministic algorithm can be competitive in general for this problem, we give an algorithm with competitive ratio that depends on the ratio of maximum weight of any edge to the capacity of the server it is incident to. If this ratio is 1/2, our algorithm is tight. Further, we give a randomized algorithm that is 6-competitive in expectation for the general problem. Most previous work on the problem and its variants assumes that the edge weights are much smaller than server capacities. Our guarantee, in contrast, does not require any assumptions about job weights. We also give improved lower bounds for both deterministic and randomized algorithms. For the special case of parallel servers, we show that a load-balancing algorithm is tight and near-optimal.

Subject Classification

Keywords
  • Online Algorithms
  • Adwords
  • Budgeted Matching
  • Greedy Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1253-1264, 2011. Google Scholar
  2. Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. The online stochastic generalized assignment problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 11-25. Springer, 2013. Google Scholar
  3. Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Algorithms-ESA 2007, pages 253-264. Springer, 2007. Google Scholar
  4. Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. Randomized primal-dual analysis of RANKING for online bipartite matching. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 101-107, 2013. Google Scholar
  5. Jon Feldman, Nitish Korula, Vahab S. Mirrokni, S. Muthukrishnan, and Martin Pál. Online ad assignment with free disposal. In Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings, pages 374-385, 2009. Google Scholar
  6. Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. Tight approximation algorithms for maximum general assignment problems. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 611-620. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  7. Bernhard Haeupler, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Online stochastic weighted matching: Improved approximation algorithms. In Internet and Network Economics - 7th International Workshop, WINE 2011, Singapore, December 11-14, 2011. Proceedings, pages 170-181, 2011. Google Scholar
  8. Bala Kalyanasundaram and Kirk Pruhs. An optimal deterministic algorithm for online b-matching. Theor. Comput. Sci., 233(1-2):319-325, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(99)00140-1.
  9. Ming-Yang Kao and Stephen R. Tate. Online matching with blocked input. Inf. Process. Lett., 38(3):113-116, 1991. Google Scholar
  10. Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 352-358, 1990. Google Scholar
  11. Nitish Korula and Martin Pál. Algorithms for secretary problems on graphs and hypergraphs. In Automata, Languages and Programming, pages 508-520. Springer, 2009. Google Scholar
  12. Benny Lehmann, Daniel J. Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270-296, 2006. Google Scholar
  13. Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22, 2007. Google Scholar
  14. Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In Foundations of Computer Science, 1977., 18th Annual Symposium on, pages 222-227. IEEE, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact