Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling

DOI10.1007/978-3-031-32726-1_18zbMath1528.90110arXiv2211.02044OpenAlexW4377199990MaRDI QIDQ6086005

Guillaume Sagnol, Daniel Schmidt genannt Waldschmidt, Philipp Warode, Sven Jäger

Publication date: 9 November 2023

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Competitive analysis of preemptive single-machine scheduling
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• Searching in the plane
• Non-clairvoyant scheduling for weighted flow time
• Dynamic scheduling on parallel machines
• Nonclairvoyant scheduling
• Lower bounds for on-line single-machine scheduling.
• Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines
• Competitive Algorithms from Competitive Equilibria
• Optimal Constructions of Hybrid Algorithms
• Speed is as powerful as clairvoyance
• A supermodular relaxation for scheduling with release dates
• Optimal on-line algorithms for single-machine scheduling
• Scheduling Parallel Machines On-Line
• Minimizing weighted flow time
• Non-Clairvoyant Precedence Constrained Scheduling.
• A Tight 2-Approximation for Preemptive Stochastic Scheduling
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• Minimizing the total completion time on-line on a single machine, using restarts
• LATIN 2004: Theoretical Informatics

This page was built for publication: Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling