Campus Event Calendar

Event Entry

What and Who

A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints

Celine Swennenhuis
TU Eindhoven
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 25 July 2023
30 Minutes
E1 4


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 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+\frac{n}{m})^{O(sqrt{nm})} time. This algorithm is subexponential when m = o(n).


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 06/22/2023 12:50 -- Created document.