Research map / Learning theory and algorithms / Sample complexity
On Preemption and Learning in Stochastic Scheduling
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 |
|---|---|---|---|
| Use preemption (ETC-RR/UCB-RR, round-robin-style exploration) instead of non-preemptive exploration (ETC-U/UCB-U) | learning algorithms for unknown job types · two job types, lambda1 small vs lambda2=1, n=50 | normalized excess cost / CR over FTPP | Helped |
| Use optimism (UCB) instead of explore-then-commit (ETC) | learning algorithms · simulations, all parameter settings | competitive ratio | Helped |
| Preemption in learning algorithms | ETC and UCB type-selection · theory, two types with well-separated means | excess cost bound | Helped |
| Non-preemptive learning algorithm vs FTPP with known types | ETC-U, UCB-U · theory, K=2, lambda2>=3lambda1 | expected cost excess over FTPP | Hurt |
Closest papers by meaning
- Scheduling jobs with stochastic holding costs (NeurIPS 2021 · similarity 0.89)
- Non-clairvoyant Scheduling with Partial Predictions (ICML 2024 · similarity 0.86)
- Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret (NeurIPS 2026 · similarity 0.85)
- Non-Clairvoyant Scheduling with Progress Bars (NeurIPS 2025 · similarity 0.84)
- DynaSchedBench: Calibrated Dynamic Scheduling Benchmarks and Observability Paradox in LLM-based Scheduling Agents (ICML 2026 · similarity 0.84)
- Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling (ICLR 2025 · similarity 0.83)
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.