Parameter-Dependent Competitive Analysis for Online Capacitated Coverage Maximization through Boostings and Attenuations

Pan Xu
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:54831-54851, 2024.

Abstract

In this paper, we consider a model called Online Capacitated Coverage Maximization, characterized by two features: (1) the dynamic arrival of online agents following a known identical and independent distribution, and (2) each offline agent is associated with a specific coverage valuation over the groundset of online agents. Additionally, both offline and online agents are assigned integer capacities, reflecting finite budgets and operational constraints. We introduce and analyze two matching policies. The first, a non-adaptive policy, utilizes offline statistics derived from solving a benchmark linear program. The second is an enhanced version equipped with real-time boostings and attenuations. We conduct a comprehensive competitive analysis and characterize the competitive ratio for both policies as functions of two crucial parameters: a lower bound on the matching capacity among offline agents and an upper bound on the number of online agents covering any specific feature for offline agents.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-xu24a, title = {Parameter-Dependent Competitive Analysis for Online Capacitated Coverage Maximization through Boostings and Attenuations}, author = {Xu, Pan}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {54831--54851}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/xu24a/xu24a.pdf}, url = {https://proceedings.mlr.press/v235/xu24a.html}, abstract = {In this paper, we consider a model called Online Capacitated Coverage Maximization, characterized by two features: (1) the dynamic arrival of online agents following a known identical and independent distribution, and (2) each offline agent is associated with a specific coverage valuation over the groundset of online agents. Additionally, both offline and online agents are assigned integer capacities, reflecting finite budgets and operational constraints. We introduce and analyze two matching policies. The first, a non-adaptive policy, utilizes offline statistics derived from solving a benchmark linear program. The second is an enhanced version equipped with real-time boostings and attenuations. We conduct a comprehensive competitive analysis and characterize the competitive ratio for both policies as functions of two crucial parameters: a lower bound on the matching capacity among offline agents and an upper bound on the number of online agents covering any specific feature for offline agents.} }
Endnote
%0 Conference Paper %T Parameter-Dependent Competitive Analysis for Online Capacitated Coverage Maximization through Boostings and Attenuations %A Pan Xu %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-xu24a %I PMLR %P 54831--54851 %U https://proceedings.mlr.press/v235/xu24a.html %V 235 %X In this paper, we consider a model called Online Capacitated Coverage Maximization, characterized by two features: (1) the dynamic arrival of online agents following a known identical and independent distribution, and (2) each offline agent is associated with a specific coverage valuation over the groundset of online agents. Additionally, both offline and online agents are assigned integer capacities, reflecting finite budgets and operational constraints. We introduce and analyze two matching policies. The first, a non-adaptive policy, utilizes offline statistics derived from solving a benchmark linear program. The second is an enhanced version equipped with real-time boostings and attenuations. We conduct a comprehensive competitive analysis and characterize the competitive ratio for both policies as functions of two crucial parameters: a lower bound on the matching capacity among offline agents and an upper bound on the number of online agents covering any specific feature for offline agents.
APA
Xu, P.. (2024). Parameter-Dependent Competitive Analysis for Online Capacitated Coverage Maximization through Boostings and Attenuations. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:54831-54851 Available from https://proceedings.mlr.press/v235/xu24a.html.

Related Material