Research map / Bandits and online learning / Online convex optimization and games
Parameter-Dependent Competitive Analysis for Online Capacitated Coverage Maximization through Boostings and Attenuations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes two LP-based matching policies (a non-adaptive SM-A and an adaptive SM-B with real-time boostings and attenuations) for online capacitated coverage maximization under KIID arrivals, giving parameter-dependent competitive ratios.
Problem
Online capacitated coverage maximization under known identical independent distribution (KIID) arrivals, where offline agents have coverage valuations and integer capacities and online agents arrive dynamically with real-time irrevocable decisions.
Approach
A non-adaptive LP-guided sampling policy, and an adaptive variant that uses real-time boostings (sampling among currently safe neighbors) plus two sequence-guided attenuations to balance matching probabilities across task-skill pairs; competitive ratios are expressed as functions of the skill-coverage parameter tau (from Delta) and the uniform capacity b.
Key results
- Non-adaptive SM-A achieves competitive ratio kappa(tau,b) and adaptive SM-B achieves eta(tau,b) >= 0.602 for all tau and b, improving over the 0.580 bound of prior work.
- For (Delta,tau)=(1,1-1/e) and b=1, SM-B attains 0.692 versus 0.632 for SM-A while Greedy is zero-competitive.
- An upper bound shows no algorithm exceeds 2-3/e (~0.896) as b grows when Delta=1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add real-time boosting and attenuations to the non-adaptive sampling policy | SM-A, yielding SM-B · OCCM (KIID), τ=0.632 (Δ=1), b=1 | competitive ratio: 0.632 -> 0.692 | Helped |
| Add real-time boosting and attenuations to the non-adaptive sampling policy | SM-A, yielding SM-B · OCCM (KIID), τ=1 (Δ=∞), b=3 | competitive ratio: 0.580+0.024 | Helped |
| Add real-time boosting and attenuations to the non-adaptive sampling policy | SM-A, yielding SM-B · OCCM (KIID), τ=0.950 (Δ=3), b=3 | competitive ratio: 0.589+0.025 | Helped |
| Add real-time boosting and attenuations to the non-adaptive sampling policy | SM-A, yielding SM-B · OCCM (KIID), τ=0.632 (Δ=1), b=∞ | competitive ratio: 0.741, 0 | No clear effect |
| Add real-time boosting and attenuations to the non-adaptive sampling policy | SM-A, yielding SM-B · OCCM (KIID), τ=1 (Δ=∞), b=∞ | competitive ratio: 0.632, 0 | No clear effect |
Surprising findings
- Greedy, which is optimal for online submodular welfare maximization, is zero-competitive for this capacitated coverage model.
- The 1-1/e barrier can be beaten when either the coverage parameter Delta is finite or capacity b is finite.
Limitations
- Analysis is theoretical; numerical evaluation on real datasets is left to future work.
- Only offline-side capacity is treated in the main text; two-sided capacity deferred to an appendix.
- Universal hardness result is established only for the special case (Delta, tau) = (1, 1-1/e).
Experimental setup
Metrics: competitive ratio adaptivity gap
Baselines: Greedy (GRY) SM-A Dickerson et al. 2019b non-adaptive policy
Builds on: Online Submodular Welfare Maximization (Kapralov et al., 2013) Xu 2023b online capacitated coverage maximization Ma et al. 2023 fairness online matching with boostings
Closest papers by meaning
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.89)
- Fully Online Matching with Stochastic Arrivals and Departures (AAAI 2023 · similarity 0.86)
- Promoting External and Internal Equities Under Ex-Ante/Ex-Post Metrics in Online Resource Allocation (ICML 2024 · similarity 0.83)
- On The Statistical Complexity of Offline Decision-Making (ICML 2024 · similarity 0.83)
- Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty (NeurIPS 2024 · similarity 0.83)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.