Name
Abstract | ||
|---|---|---|
We consider a two-stage robust facility location problem on a metric under an uncertain demand. The decision-maker needs to decide on the (integral) units of supply for each facility in the first stage to satisfy an uncertain second-stage demand, such that the sum of first stage supply cost and the worst-case cost of satisfying the second-stage demand over all scenarios is minimized. The second-stage decisions are only assignment decisions without the possibility of adding recourse supply capacity. This makes our model different from existing work on two-stage robust facility location and set covering problems. We consider an implicit model of uncertainty with an exponential number of demand scenarios specified by an upper bound $k$ on the number of second-stage clients. In an optimal solution, the second-stage assignment decisions depend on the scenario; surprisingly, we show that restricting to a fixed (static) fractional assignment for each potential client irrespective of the scenario gives us an $O(\log k/\log \log k)$-approximation for the problem. Moreover, the best such static assignment can be computed efficiently giving us the desired guarantee. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-73879-2_18 | IPCO |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| El Housni, Omar | 1 | 0 | 1.35 |
| Vineet Goyal | 2 | 156 | 10.88 |
| David B. Shmoys | 3 | 4829 | 601.03 |