Online interval scheduling with predictions

DOI10.1007/978-3-031-38906-1_14arXiv2302.13701MaRDI QIDQ6179410

Kim S. Larsen, Lene Monrad Favrholdt, Shahin Kamali, Joan. Boyar

Publication date: 16 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2302.13701

zbMATH Keywords

competitive analysisdisjoint pathsonline interval schedulingalgorithms with prediction

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Edge-disjoint paths in planar graphs
• The advice complexity of a class of hard online problems
• A linear-time algorithm for edge-disjoint paths in planar graphs
• Call admission problems on grids with advice
• Call admission problems on trees
• On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
• Disjoint Path Allocation with Sublinear Advice
• Interval scheduling: A survey
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• On the Complexity of Timetable and Multicommodity Flow Problems
• Algorithms with Predictions
• Competitive Caching with Machine Learned Advice
• Near-Optimal Bounds for Online Caching with Machine Learned Advice
• Online Scheduling via Learned Weights
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Flow time scheduling with uncertain processing time
• Secretary and online matching problems with machine learned advice