Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 20-minute IEEE conference talk on scheduling precedence-constrained jobs on related machines with communication delay. Learn about duplication techniques, heterogeneous processing, and the challenges of delay constraints. Discover the makespan algorithm, integrality gap, and LP relaxation approaches. Gain insights into the main results, techniques, and open problems in this field of study presented by researchers from Northeastern University, Google, and Northwestern University.
Syllabus
Intro
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
Precedence-Constrained Scheduling on
Duplication A job is duplicated it is cute on multiple machines Duplication can be helpful in prence of communication delay
Motivation: Heterogenous Processing
Prior & Related Work
Central Question
Makespan Algorithm
Integrality Gap
Bounding the Duplication Advantage
Challenges: Delay Constraints
LP Relaxation
Algorithm Overview
Iterative Scheduling
Lower Bound
Main Result & Techniques
Open Problems
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube