Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Shifting coresets: obtaining linear-time approximations for unit disk
  graphs and other geometric intersection graphs   Numerous approximation algorithms for problems on unit disk graphs have been
proposed in the literature, exhibiting a sharp trade-off between running times
and approximation ratios. We introduce a variation of the known shifting
strategy that allows us to obtain linear-time constant-factor approximation
algorithms for such problems. To illustrate the applicability of the proposed
variation, we obtain results for three well-known optimization problems. Among
such results, the proposed method yields linear-time (4+eps)-approximation for
the maximum-weight independent set and the minimum dominating set of unit disk
graphs, thus bringing significant performance improvements when compared to
previous algorithms that achieve the same approximation ratios. Finally, we use
axis-aligned rectangles to illustrate that the same method may be used to
derive linear-time approximations for problems on other geometric intersection
graph classes.

25
The categories of this paper are: patt-sol
24
The categories of this paper are: dg-ga
26
The categories of this paper are: bayes-an
33
The categories of this paper are: plasm-ph
8
The categories of this paper are: hep-ex
13
The categories of this paper are: quant-ph
16
The categories of this paper are: stat
19
The categories of this paper are: eess
37
The categories of this paper are: supr-con
23
The categories of this paper are: solv-int
5
The categories of this paper are: gr-qc
21
The categories of this paper are: adap-org
9
The categories of this paper are: nlin
7
The categories of this paper are: hep-th
20
The categories of this paper are: acc-phys
12
The categories of this paper are: nucl-th