We are delighted to announce the talk given by Klaus Heeger (Ben Gurion
University).
The title is " Minimizing the Weighted Number of Tardy Jobs is W[1]-hard ".
The seminar will take place on Zoom on Wednesday, January 24 at 14:00 UTC.
Join Zoom Meeting
https://cesnet.zoom.us/j/92404235122?pwd=cFVxSVBPS28wS3dhYVQ5WVhJcEVkUT09
Meeting ID: 924 0423 5122
Passcode: 536766
You can follow the seminar online or offline on our Youtube channel as well:
https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A
The abstract follows.
We consider the 1 || ∑ wj Uj problem, the problem of minimizing the
weighted number of tardy jobs on a single machine. This problem is one
of the most basic and fundamental problems in scheduling theory, with
several different applications both in theory and practice. We prove
that 1 || ∑ wj Uj is W[1]-hard with respect to the number of different
processing times in the input, as well as with respect to the number of
different weights in the input. This, along with previous work, provides
a complete picture for 1 || ∑ wj Uj from the perspective of
parameterized complexity, as well as almost tight complexity bounds for
the problem under the Exponential Time Hypothesis (ETH). Based on joint
work with Danny Hermelin.
The next talk in our series will be:
Ceyda Oğuz (Koç University) | February 7 | A Matheuristic for the
Generalized Order Acceptance and Scheduling Problem.
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
