Research map / Bandits and online learning / Online convex optimization and games
Data-driven Competitive Algorithms for Online Knapsack and Set Cover
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Select the policy parameter using the previous instance instead of fixing it at the worst-case optimized setting | OKP-Alg(1), EV admission control · EV admission control | average improvement over OKP-Alg(1): 17.8\% | Helped |
| Select the policy parameter using the previous instance instead of fixing it at the worst-case optimized setting | OKP-Alg(1), EV admission control · EV admission control | empirical profit ratio: 1.87 -> 1.46 | Mixed |
| Use the optimal policy of the previous instance | OKP-Alg(1), EV admission control · EV admission control | instances with worse performance: 3\% | Mixed |
| Vary the OKP threshold growth parameter away from 1 (ablation) | OKP-Alg(1) · Online knapsack | degradation factor | Hurt |
| Use a larger theta, selecting more subsets per round (ablation) | OSC-Alg(theta) · Online set cover, high-overlap scenario | normalized cost | Helped |
| Use a larger theta, selecting more subsets per round (ablation) | OSC-Alg(theta) · Online set cover, low-overlap scenario | normalized cost | Hurt |
| Tune theta within the policy class rather than using theta = 2 (ablation) | OSC-Alg(2) · Online set cover | degradation factor: less than 1 | Helped |
Closest papers by meaning
- Contextual Decision-Making with Knapsacks Beyond the Worst Case (NeurIPS 2024 · similarity 0.87)
- Time Fairness in Online Knapsack Problems (ICLR 2024 · similarity 0.87)
- Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems (ICML 2025 · similarity 0.86)
- Augmenting Online Algorithms for Knapsack Problem with Total Weight Information (AAAI 2025 · similarity 0.86)
- Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search (ICML 2025 · similarity 0.85)
- Bandits with Replenishable Knapsacks: the Best of both Worlds (ICLR 2024 · similarity 0.85)
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.