Research map / Learning theory and algorithms / Prediction and decision losses
Advice Querying under Budget Constraint for Online Algorithms
Ziyad Benomar, Vianney Perchet
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| query the prediction after renting t days instead of at t=0 (deterministic Algorithm 1) | Ski-rental with time-dependent oracle accuracy · Ski rental, b=50,100, pt=0.95-0.4exp(-t/5) | competitive ratio | Improved |
| query the prediction after renting t days (randomized Algorithm 2) with b=50 | Ski-rental randomized algorithm · Ski rental, b=50 | competitive ratio | No clear effect |
| use randomized instead of deterministic algorithm after the binary prediction | Ski-rental with accuracy-p oracle · Ski rental, p in (0.5,1) | competitive ratio bound | Improved |
| use randomized instead of deterministic algorithm when oracle accuracy p is very close to 1 | Ski-rental with accuracy-p oracle · Ski rental, p near 1 | competitive ratio bound: 1 + 1/b instead of 1 | Hurt |
| tune lambda optimally as a function of p instead of fixed lambda | Algorithm 1 deterministic ski rental · Ski rental, p>=0.5 | competitive ratio bound: 1 + 2sqrt(p(1-p)) <= 2 | Improved |
| compare experimental to theoretical competitive ratio of deterministic Algorithm 1 | Algorithm 1 · Ski rental b=50, x~U[1,4b] | competitive ratio | Improved |
| increase prediction budget B in ADATHRESH | ADATHRESH secretary algorithm · Secretary, N=1000, B<=20 | success probability | Improved |
| add memory of the best observed value after restart | ADATHRESH · Secretary, N=1000 | success probability | Improved |
| increase oracle accuracy p toward 1 in imperfect-prediction ADATHRESH | ADATHRESH with noisy oracle · Secretary, B<=20 | success probability lower bound qB(p): limit 1 - 1/(1 + W(p/(e(1-p)))) | Improved |
| trust oracle only if p above about 0.73, else use 1/e-rule | ADATHRESH with noisy oracle · Secretary | success probability: qB(p)=1/e for p <= 0.73 | Improved |
| query job sizes of B jobs only after waiting or running RR first | B-clairvoyant scheduling · Non-clairvoyant scheduling | competitive ratio: 2 | No clear effect |
| give sublinear B=o(N) job-size queries | Preemptive non-clairvoyant scheduling · Scheduling lower bound | competitive ratio: 2 | No clear effect |
Closest papers by meaning
- Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints (ICML 2023 · similarity 0.89)
- Improving Online Algorithms via ML Predictions (NeurIPS 2018 · similarity 0.88)
- Non-clairvoyant Scheduling with Partial Predictions (ICML 2024 · similarity 0.86)
- Online Algorithms with Uncertainty-Quantified Predictions (ICML 2024 · similarity 0.86)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.85)
- Improved Bounds for Online Facility Location with Predictions (AAAI 2025 · 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.
