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/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
