Scheduling seminar

Download

schedulingseminar@rtime.felk.cvut.cz

December 2023

1 participants
1 discussions

Céline Swennenhuis (ALGO, TU Eindhoven) | December 13 | A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
by Zdeněk Hanzálek 11 Dec '23

11 Dec '23

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 -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0