Further talks

×

Modal title

Modal content

Spring Semester 2020

Date / Time

Speaker

Title

Location

6 February 2020
13:30-14:30

Dr. Silvio Lattanzi
Google Research Zurich

Details

IFOR talks

Title	Online Scheduling via Learned Weights
Speaker, Affiliation	Dr. Silvio Lattanzi, Google Research Zurich
Date, Time	6 February 2020, 13:30-14:30
Location	HG G 26.1
Abstract	Online algorithms are a hallmark of worst case optimization under uncertainty. On the other hand, in practice, the input is often far from the worst case, and has some predictable characteristics. A recent line of work has shown how to use machine learned predictions to circumvent strong lower bounds on competitive ratios in classic online problems such as ski rental and caching. We study how predictive techniques can be used to break through worst case barriers in online scheduling. The makespan minimization problem with restricted assignments is a classic problem in online scheduling theory. Worst case analysis of this problem gives $\Omega(\log m)$ lower bounds on the competitive ratio in the online setting. We identify a robust quantity that can be predicted and then used to guide online algorithms to achieve better performance. Our predictions are compact in size, having dimension linear in the number of machines, and can be learned using standard off the shelf methods. The performance guarantees of our algorithms depend on the accuracy of the predictions, given predictions with error $\eta$, we show how to construct $O(\log \eta)$ competitive fractional assignments. We then give an online algorithm that rounds any fractional assignment into an integral schedule. Our algorithm is $O((\log\log m)^3)$-competitive and we give a nearly matching $\tilde{\Omega}(\log\log m)$ lower bound for online rounding algorithms.\footnote{We use $\tilde{O}(f(m))$ and $\tilde{\Omega}(f(m))$ notations to suppress factors of $\log^c f(m)$ for constant $c$.} Altogether, we give algorithms that, equipped with predictions with error $\eta$, achieve $O(\log \eta\ (\log \log m)^3)$ competitive ratios, breaking the $\Omega(\log m)$ lower bound even for moderately accurate predictions. Joint work with T. Lavastida, B. Moseley and S. Vassilvitskii

Online Scheduling via Learned Weightsread_more

Notes: wenn Sie möchten, können Sie den iCal/ics-Kalender abonnieren.

Archive: undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined