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

Given a set ${\cal R}=\{R_1,R_2,..., R_n\}$ of $n$ randomly positioned axisparallel rectangles in 2D, the problem of computing the minimum clique cover(MCC) and maximum independent set (MIS) for the intersection graph $G({\calR})$ of the members in $\cal R$ are both computationally hard \cite{CC05}. Forthe MCC problem, it is proved that polynomial time constant factorapproximation is impossible to obtain \cite{PT11}. Though such a result is notproved yet for the MIS problem, no polynomial time constant factorapproximation algorithm exists in the literature. We study the performance ofgreedy algorithms for computing these two parameters of $G({\cal R})$.Experimental results shows that for each of the MCC and MIS problems, thecorresponding greedy algorithm produces a solution that is very close to itsoptimum solution. Scheinerman \cite{Scheinerman80} showed that the size of MISis tightly bounded by $\sqrt{n}$ for a random instance of the 1D version of theproblem, (i.e., for the interval graph). Our experiment shows that the size ofindependent set and the clique cover produced by the greedy algorithm is atleast $2\sqrt{n}$ and at most $3\sqrt{n}$, respectively. Thus theexperimentally obtained approximation ratio of the greedy algorithm for MISproblem is at most 3/2 and the same for the MCC problem is at least 2/3.Finally we will provide refined greedy algorithms based on a concept of {\itsimplicial rectangle}. The characteristics of this algorithm may be of interestin getting a provably constant factor approximation algorithm for randominstance of both the problems. We believe that the result also holds true forany finite dimension.

Greedy is good: An experimental study on minimum clique cover and maximum independent set problems for randomly generated rectangles