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 rectangle stabbing problem, we are given a set $\cR$ of axis-alignedrectangles in $\RR^2$, and the objective is to find a minimum-cardinality setof horizontal and/or vertical lines such that each rectangle is intersected byone of these lines. The standard LP relaxation for this problem is known tohave an integrality gap of 2, while a better intergality gap of 1.58.. is knownfor the special case when $\cR$ is a set of horizontal segments. In this paper,we consider two more special cases: when $\cR$ is a set of horizontal andvertical segments, and when $\cR$ is a set of unit squares. We show that theintegrality gap of the standard LP relaxation in both cases is stricly lessthan $2$. Our rounding technique is based on a generalization of the {\itthreshold rounding} idea used by Kovaleva and Spieksma (SIAM J. Disc. Math2006), which may prove useful for rounding the LP relaxations of othergeometric covering problems.

Threshold Rounding for the Standard LP Relaxation of some Geometric Stabbing Problems