2 papers
cs.DS2023
Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs
Sven Jäger, Philipp Warode
We consider the precedence-constrained scheduling problem to minimize the total weighted completion time. For a single machine several -approximation algorithms are known, which…
cs.DS2022
Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling
Sven Jäger, Guillaume Sagnol, Daniel Schmidt genannt Waldschmidt +1
We study kill-and-restart and preemptive strategies for the fundamental scheduling problem of minimizing the sum of weighted completion times on a single machine in the non-clairvo…