Online Facility Location with Predictions
401
26.7
Microsoft Research320 тыс
Следующее
14.12.22 – 4951:36:23Популярные
141 день – 1 55932:52
13.02.23 – 3 36557:57Опубликовано 12 декабря 2022, 20:34
2022 Data-driven Optimization Workshop: Online Facility Location with Predictions
Speaker: Shaofeng Jiang, Peking University
In this talk, we present a nearly optimal algorithm for online facility location (OFL) with (untrusted) predictions. In OFL, n demand points arrive in order and the algorithm must irrevocably assign each demand point to an open facility upon its arrival. The objective is to minimize the total connection costs from demand points to assigned facilities, plus the facility opening cost.
We additionally assume an untrusted predictor can suggest the facility that a demand point should be assigned to. With the access to this predictor but without knowing the error of the prediction, our algorithm achieves O(1) ratio when the error is small, which bypasses a \Omega(log n / log log n) worst-case lower bound. Furthermore, our algorithm still maintains O(log n) ratio even when the error is unbounded, nearly matching the mentioned lower bound.
Based on a joint work with Erzhi Liu, You Lyu, Zhihao Tang and Yubo Zhang.
Speaker: Shaofeng Jiang, Peking University
In this talk, we present a nearly optimal algorithm for online facility location (OFL) with (untrusted) predictions. In OFL, n demand points arrive in order and the algorithm must irrevocably assign each demand point to an open facility upon its arrival. The objective is to minimize the total connection costs from demand points to assigned facilities, plus the facility opening cost.
We additionally assume an untrusted predictor can suggest the facility that a demand point should be assigned to. With the access to this predictor but without knowing the error of the prediction, our algorithm achieves O(1) ratio when the error is small, which bypasses a \Omega(log n / log log n) worst-case lower bound. Furthermore, our algorithm still maintains O(log n) ratio even when the error is unbounded, nearly matching the mentioned lower bound.
Based on a joint work with Erzhi Liu, You Lyu, Zhihao Tang and Yubo Zhang.
Свежие видео
2 дня – 2561:33
3 дня – 3523:36
3 дня – 1041:05
6 дней – 2300:49
6 дней – 1 1850:24
9 дней – 6 3040:21Случайные видео
213 дней – 13 4730:43
233 дня – 706:31
31.12.22 – 110 4686:40
04.05.20 – 129 4058:37
14.04.20 – 75 7362:50
24.08.11 – 86 3622:09
2 дня – 2 3381:43
2 дня – 1 1341:51
3 дня – 16 17541:39
6 дней – 80 5010:46
7 дней – 7 3930:17
8 дней – 2276:46
9 дней – 413:40
1 день – 7940:51
1 день – 7528:16