Главная
Study mode:
on
1
Intro
2
Load Balancing Problem
3
Load Balancing (Formally)
4
Optimization under Uncertainty
5
Stochastic Load Balancing
6
Natural Approach for Stochastic Optimization
7
Deterministic Surrogate for Load Balancing?
8
Related Work: Deterministic Job Sizes
9
Related Work: Stochastic Job Sizes
10
Main Results
11
Further Complication
12
Effective Size: Unrelated Machines
13
Approach in Deterministic Setting
14
Our Approach in Stochastic Setting
15
Valid Inequalities
16
LP Relaxation
17
Algorithm Outline
18
Rounding Overview
19
Generalized Assignment Problem
20
Rounding Algorithm: Constructing GAP Instance
21
Analysis Outline
Description:
Explore a lecture on stochastic load balancing for unrelated machines, delivered by Viswanath Nagarajan at the Hausdorff Center for Mathematics. Delve into the first constant factor approximation algorithm for minimizing expected makespan in unrelated machine scheduling with stochastic job processing times. Examine the efficiently computable lower bound via an exponential-sized LP and its rounding technique. Follow the progression from the problem introduction to the analysis of the proposed algorithm, covering topics such as optimization under uncertainty, effective size for unrelated machines, LP relaxation, and the generalized assignment problem. Gain insights into this previously open problem, even for related machines, and understand its significance in combinatorial optimization.

Viswanath Nagarajan - Stochastic Load Balancing on Unrelated Machines

Hausdorff Center for Mathematics
Add to list
0:00 / 0:00