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
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 25 July 2023
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
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).
Contact
Roohani Sharma
+49 681 9325 1116
--email hidden
Virtual Meeting Details
Zoom
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 rsharma@mpi-inf.mpg.de.
Roohani Sharma, 06/22/2023 12:50 -- Created document.