Online Facility Location with Predictions
439
29.3
Microsoft Research334 тыс
Следующее
14.12.22 – 5181:36:23Популярные
353 дня – 17022:21
26.09.23 – 2 0291:18Опубликовано 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.
Свежие видео
10 дней – 48510:58
11 дней – 2 1621:11
12 дней – 116 4418:23
13 дней – 1 3950:42
14 дней – 4491:36Случайные видео
58 дней – 3 5170:27
62 дня – 12 0411:00
245 дней – 805 7143:29:35
351 день – 3 6982:30
11.12.20 – 330 23710:47
21.02.14 – 7 1392:02:46
8 часов – 8071:46
13 часов – 62211:52
1 день – 2 06417:41
2 дня – 4289:29
3 дня – 1 1300:09
4 дня – 278 8611:00
5 дней – 43 09715:40
7 дней – 7460:34