Online Facility Location with Predictions
444
29.6
Microsoft Research335 тыс
Следующее
14.12.22 – 5191:36:23Популярные
11.11.23 – 5571:08:45
12.12.22 – 1 67830:07Опубликовано 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.
Свежие видео
9 дней – 5180:20
13 дней – 86 81817:41
13 дней – 802:30
20 дней – 5760:05
20 дней – 45 9720:26
21 день – 9110:07Случайные видео
230 дней – 1 34210:16
245 дней – 5 8050:55
30.11.23 – 6 8560:12
28.08.22 – 3 259 6970:35
03.08.21 – 17 68651:34
4 дня – 2 3754:31
9 дней – 1 278 2188:01
10 дней – 347 02811:22
11 дней – 6 4439:19
13 дней – 1 01429:31
13 дней – 8 4200:36
1 день – 5100:21
5 дней – 1493:07