English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we study the facility location problem in the online withrecourse and dynamic algorithm models. In the online with recourse model,clients arrive one by one and our algorithm needs to maintain good solutions atall time steps with only a few changes to the previously made decisions (calledrecourse). We show that the classic local search technique can lead to a$(1+\sqrt{2}+\epsilon)$-competitive online algorithm for facility location withonly $O\left(\frac{\log n}{\epsilon}\log\frac1\epsilon\right)$ amortizedfacility and client recourse. We then turn to the dynamic algorithm model forthe problem, where the main goal is to design fast algorithms that maintaingood solutions at all time steps. We show that the result for online facilitylocation, combined with the randomized local search technique of Charikar andGuha [10], leads to an $O(1+\sqrt{2}+\epsilon)$ approximation dynamic algorithmwith amortized update time of $\tilde O(n)$ in the incremental setting. Noticethat the running time is almost optimal, since in general metric space it takes$\Omega(n)$ time to specify a new client's position. The approximation factorof our algorithm also matches the best offline analysis of the classic localsearch algorithm. Finally, we study the fully dynamic model for facilitylocation, where clients can both arrive and depart. Our main result is an$O(1)$-approximation algorithm in this model with $O(|F|)$ preprocessing timeand $O(\log^3 D)$ amortized update time for the HST metric spaces. Using theseminal results of Bartal [4] and Fakcharoenphol, Rao and Talwar [17], whichshow that any arbitrary $N$-point metric space can be embedded into adistribution over HSTs such that the expected distortion is at most $O(\logN)$, we obtain a $O(\log |F|)$ approximation with preprocessing time of$O(|F|^2\log |F|)$ and $O(\log^3 D)$ amortized update time.

The Power of Recourse: Better Algorithms for Facility Location in Online and Dynamic Models