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 the Independent Set of Convex Polygons problem we are given a set of weighted convex polygons in the plane and we want to compute a maximum weight subset of non-overlapping polygons. This is a very natural and well-studied problem with applications in many different areas. Unfortunately, there is a very large gap between the known upper and lower bounds for this problem. The best polynomial time algorithm we know has an approximation ratio of  and the best known lower bound shows only strong -hardness. In this paper we close this gap, assuming that we are allowed to shrink the polygons a little bit, by a factor  for an arbitrarily small constant , while the compared optimal solution cannot do this (resource augmentation). In this setting, we improve the approximation ratio of  to  which matches the above lower bound that still holds if we can shrink the polygons.

Independent Set of Convex Polygons: From $$n^{\epsilon }$$ n ϵ to $$1+\epsilon $$ 1 + ϵ via Shrinking