Research map / Bandits and online learning / Online convex optimization and games
Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints
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 |
|---|---|---|---|
| Provide correct static total-weight predictions for chains | Non-clairvoyant online scheduling · Online chains | competitive ratio: Ω(n) -> 4 | Helped |
| Provide correct adaptive total-weight predictions | Non-clairvoyant online scheduling · Online out-forests | competitive ratio: 4 | Helped |
| Use adaptive weight-order predictions instead of exact weight values | Online out-forest scheduling · Online out-forests | competitive ratio: 4 H_ω | Helped |
| Use static rather than adaptive weight-order predictions | Adaptive weight-order algorithm · Online chains | competitive ratio: O(H^2_ω √P) | Hurt |
| Provide adaptive average-weight predictions instead of total-weight predictions | Non-clairvoyant online scheduling · Online chains with unit jobs | competitive ratio: Ω(√n) | Hurt |
| Use static weight predictions on out-trees rather than chains | Non-clairvoyant online scheduling · Online out-trees | competitive ratio: Ω(n) | Hurt |
| Use adaptive weight predictions on in-trees rather than out-forests | Non-clairvoyant online scheduling · Online in-trees | competitive ratio: Ω(√n) | Hurt |
| Use full input predictions for unit-size jobs on chains | Non-clairvoyant online scheduling · Online chains | competitive ratio: O(min {1 + Λ, ω}) | Helped |
| Use time-sharing with the width-competitive fallback | Prediction-dependent scheduling algorithms · Online precedence constraints | competitive ratio: 2 · min{ρ_A, ρ_B} | Helped |
Closest papers by meaning
- Non-clairvoyant Scheduling with Partial Predictions (ICML 2024 · similarity 0.93)
- On Smoothness Bounds for Non-Clairvoyant Scheduling with Predictions (ICLR 2026 · similarity 0.91)
- Non-Clairvoyant Scheduling with Progress Bars (NeurIPS 2025 · similarity 0.88)
- Improved Bounds for Online Facility Location with Predictions (AAAI 2025 · similarity 0.86)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.84)
- Learning Augmented Exact Exponential Algorithms (NeurIPS 2026 · similarity 0.84)
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.