Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities

Authors Susanne Albers, Sebastian Schubert



PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.4.pdf
  • Filesize: 0.75 MB
  • 16 pages

Document Identifiers

Author Details

Susanne Albers
  • Department of Computer Science, Technische Universität München, Germany
Sebastian Schubert
  • Department of Computer Science, Technische Universität München, Germany

Cite As Get BibTex

Susanne Albers and Sebastian Schubert. Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.4

Abstract

We study the b-matching problem in bipartite graphs G = (S,R,E). Each vertex s ∈ S is a server with individual capacity b_s. The vertices r ∈ R are requests that arrive online and must be assigned instantly to an eligible server. The goal is to maximize the size of the constructed matching. We assume that G is a (k,d)-graph [J. Naor and D. Wajc, 2018], where k specifies a lower bound on the degree of each server and d is an upper bound on the degree of each request. This setting models matching problems in timely applications.
We present tight upper and lower bounds on the performance of deterministic online algorithms. In particular, we develop a new online algorithm via a primal-dual analysis. The optimal competitive ratio tends to 1, for arbitrary k ≥ d, as the server capacities increase. Hence, nearly optimal solutions can be computed online. Our results also hold for the vertex-weighted problem extension, and thus for AdWords and auction problems in which each bidder issues individual, equally valued bids.
Our bounds improve the previous best competitive ratios. The asymptotic competitiveness of 1 is a significant improvement over the previous factor of 1-1/e^{k/d}, for the interesting range where k/d ≥ 1 is small. Recall that 1-1/e ≈ 0.63. Matching problems that admit a competitive ratio arbitrarily close to 1 are rare. Prior results rely on randomization or probabilistic input models.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • online algorithms
  • deterministic algorithms
  • primal-dual analysis
  • b-matching
  • bounded-degree graph
  • variable vertex capacities
  • unweighted matching
  • vertex-weighted matching

Metrics

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

References

  1. G. Aggarwal, G. Goel, C. Karande, and A. Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1253-1264. SIAM, 2011. Google Scholar
  2. Y. Azar, I.R. Cohen, and A. Roytman. Online lower bounds via duality. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1038-1050. SIAM, 2017. Google Scholar
  3. N. Buchbinder, K. Jain, and J. Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proc. 15th Annual European Symposium on Algorithms (ESA), Springer LNCS, Volume 4698, pages 253-264, 2007. Google Scholar
  4. K. Chaudhuri, C. Daskalakis, R.D. Kleinberg, and H. Lin. Online bipartite perfect matching with augmentations. In Proc. 28th IEEE International Conference on Computer Communications (INFOCOM), pages 1044-1052, 2009. Google Scholar
  5. I.R. Cohen and D. Wajc. Randomized online matching in regular graphs. In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 960-979. SIAM, 2018. Google Scholar
  6. R. Cole, K. Ost, and S. Schirra. Edge-coloring bipartite multigraphs in O(E log D) time. Comb., 21(1):5-12, 2001. Google Scholar
  7. J. Csima and L. Lovász. A matching algorithm for regular bipartite graphs. Discret. Appl. Math., 35(3):197-203, 1992. Google Scholar
  8. N.R. Devanur and T.P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proc. 10th ACM Conference on Electronic Commerce (EC), pages 71-78. ACM, 2009. Google Scholar
  9. N.R. Devanur, B. Sivan, and Y. Azar. Asymptotically optimal algorithm for stochastic adwords. In Proc. 13th ACM Conference on Electronic Commerce (EC), pages 388-404. ACM, 2012. Google Scholar
  10. A. Goel, M. Kapralov, and S. Khanna. Perfect matchings in O(nlog n) time in regular bipartite graphs. SIAM J. Comput., 42(3):1392-1404, 2013. Google Scholar
  11. R.L. Graham, D.E. Knuth, and O. Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 1989. Google Scholar
  12. E.F. Grove, M.-Y. Kao, P. Krishnan, and J.S. Vitter. Online perfect matching and mobile computing. In Proc. 4th International Workshop on Algorithms and Data Structures (WADS), LNCS, Volume 955, pages 194-205. Springer, 1995. Google Scholar
  13. P. Jaillet and X. Lu. Online stochastic matching: New algorithms with better bounds. Math. Oper. Res., 39(3):624-646, 2014. Google Scholar
  14. B. Kalyanasundaram and K. Pruhs. An optimal deterministic algorithm for online b-matching. Theor. Comput. Sci., 233(1-2):319-325, 2000. Google Scholar
  15. R.M. Karp, U.V. Vazirani, and V.V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352-358, 1990. Google Scholar
  16. M. Mahdian and Q. Yan. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs. In Proc. 43rd ACM Symposium on Theory of Computing (STOC), pages 597-606, 2011. Google Scholar
  17. V.H. Manshadi, S. Oveis Gharan, and A. Saberi. Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res., 37(4):559-573, 2012. Google Scholar
  18. A. Mehta, A. Saberi, U.V. Vazirani, and V.V. Vazirani. Adwords and generalized online matching. J. ACM, 54(5):22, 2007. Google Scholar
  19. J. Naor and D. Wajc. Near-optimum online ad allocation for targeted advertising. ACM Trans. Economics and Comput., 6(3-4):16:1-16:20, 2018. Google Scholar
  20. A. Schrijver. Bipartite edge coloring in O(Δ m) time. SIAM J. Comput., 28(3):841-846, 1998. Google Scholar
  21. V.V. Vazirani. Randomized online algorithms for Adwords. CoRR, abs/2107.10777, 2021. URL: http://arxiv.org/abs/2107.10777.
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