We are delighted to announce the talk given by Clifford Stein (Columbia
Uni).
The title is "Scheduling with Speed Predictions".
The seminar will take place on Zoom on Wednesday, October 26 at 13:00 UTC.
Join Zoom Meeting
https://cesnet.zoom.us/j/91581329122?pwd=M0M4d2tSMXpvb1NkRGhHOVoxWG5vUT09
<https://cesnet.zoom.us/j/91581329122?pwd=M0M4d2tSMXpvb1NkRGhHOVoxWG5vUT09>
Meeting ID: 915 8132 9122
Passcode: 596335
You can follow the seminar online or offline on our Youtube channel as well:
https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A
The abstract follows.
Algorithms with predictions is a recent framework that has been used to
overcome pessimistic worst-case bounds in incomplete information
settings. In the context of scheduling, very recent work has leveraged
machine-learned predictions to design algorithms that achieve improved
approximation ratios in settings where the processing times of the jobs
are initially unknown. We study the speed-robust scheduling problem
where the speeds of the machines, instead of the processing times of the
jobs, are unknown and augment this problem with predictions. In this
talk, we give an algorithm that simultaneously achieves, for any x < 1,
a 1 + x approximation when the predictions are accurate and a 2+ 2/x
approximation when the predictions are not accurate. We also study
special cases and evaluate our algorithms performance as a function of
the error.
Joint work with Eric Balanski, TingTing Ou and Hao-Ting Wei, all at
Columbia.
The next talk in our series will be:
Alessandro Agnetis (University of Siena) | November 9 | Scheduling
machines subject to unrecoverable failures and other related stochastic
sequencing problems.
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
