Skip to yearly menu bar Skip to main content


Poster

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

Pan Xu


Abstract: In this paper, we consider a model, called *Online Capacitated Coverage Maximization* (**OCCM**), defined by two fundamental features: (1) the dynamic arrival of online agents following a known identical and independent distribution, and (2) a specific coverage valuation associated with each offline agent over the groundset of online agents. Furthermore, both offline and online agents are subject to integer matching capacities, reflecting finite budgets and operational constraints.We introduce and analyze two matching policies in this study. The first, a non-adaptive policy (SM-A), utilizes offline statistics derived from solving a benchmark Linear Program (LP). The second, an enhanced version of SM-A (SM-B), integrates real-time boostings. Our comprehensive competitive analysis characterizes the competitive ratio (CR) for both policies as a function of two crucial parameters: a lower bound on matching capacity among offline agents (referred to as $b$) and an upper bound on the number of online agents covering any specific feature for offline agents (referred to as $\Delta$). Our findings reveal that in practical scenarios where both $b$ and $\Delta$ take small finite values, the natural Greedy policy can perform arbitrarily poorly, achieving zero competitiveness. In contrast, both SM-A and SM-B consistently surpass the golden barrier of $1-1/e$. Additionally, we provide upper bounds on CR, complementing the derived lower bounds.

Live content is unavailable. Log in and register to view live content