Dear scheduling researcher, We are delighted to announce the talk given by Céline Swennenhuis (ALGO, TU Eindhoven). The title is "A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints". The seminar will take place on Zoom on Wednesday, December 13 at 14:00 UTC.
Join Zoom Meeting https://cesnet.zoom.us/j/98061412979?pwd=UVVmTnhnOHpiMUg2bW5pVFlHSENXdz09 Meeting ID: 980 6141 2979 Passcode: 208805
You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A
The abstract follows. In a classical scheduling problem, we are given a set of n jobs of unit length along with precedence constraints, and the goal is to find a schedule of these jobs on m identical parallel machines that minimizes the makespan. Using the standard 3-field notation, it is known as Pm|prec, p_j=1|Cmax. Settling the complexity of Pm|prec, p_j=1|Cmax even for m=3 machines is, together with Subgraph Isomorphism, among the last two open problems from the book of Garey and Johnson [GJ79] for which the computational complexity remains a mystery. We present an algorithm for this problem that runs in (1 + n/m)^{O(√(nm))} time, which is subexponential when m=o(n). For m=3, this equals a runtime of 2^{O(√(n)log(n))} time.
The next talk in our series will be in January. Stay tuned. For more details, please visit https://schedulingseminar.com/
With kind regards
Zdenek, Mike and Guohua