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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

A fundamental question is whether one can maintain a maximum independent setin polylogarithmic update time for a dynamic collection of geometric objects inEuclidean space. Already, for a set of intervals, it is known that no dynamicalgorithm can maintain an exact maximum independent set in sublinear updatetime. Therefore, the typical objective is to explore the trade-off betweenupdate time and solution size. Substantial efforts have been made in recentyears to understand this question for various families of geometric objects,such as intervals, hypercubes, hyperrectangles, and fat objects.  We present the first fully dynamic approximation algorithm for disks ofarbitrary radii in the plane that maintains a constant-factor approximatemaximum independent set in polylogarithmic expected amortized update time.Moreover, for a fully dynamic set of $n$ disks of unit radius in the plane, weshow that a $12$-approximate maximum independent set can be maintained withworst-case update time $O(\log n)$, and optimal output-sensitive reporting.This result generalizes to fat objects of comparable sizes in any fixeddimension $d$, where the approximation ratio depends on the dimension and thefatness parameter. Further, we note that, even for a dynamic set of disks ofunit radius in the plane, it is impossible to maintain$O(1+\varepsilon)$-approximate maximum independent set in truly sublinearupdate time, under standard complexity assumptions.

Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time