Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Graph Clustering in All Parameter Regimes   Resolution parameters in graph clustering represent a size and quality
trade-off. We address the task of efficiently solving a parameterized graph
clustering objective for all values of a resolution parameter. Specifically, we
consider an objective we call LambdaPrime, involving a parameter $\lambda \in
(0,1)$. This objective is related to other parameterized clustering problems,
such as parametric generalizations of modularity, and captures a number of
specific clustering problems as special cases, including sparsest cut and
cluster deletion. While previous work provides approximation results for a
single resolution parameter, we seek a set of approximately optimal clusterings
for all values of $\lambda$ in polynomial time. In particular, we ask the
question, how small a family of clusterings suffices to optimize -- or to
approximately optimize -- the LambdaPrime objective over the full possible
spectrum of $\lambda$?
  We obtain a family of logarithmically many clusterings by solving the
parametric linear programming relaxation of LambdaPrime at a logarithmic number
of parameter values, and round their solutions using existing approximation
algorithms. We prove that this number is tight up to a constant factor.
Specifically, for a certain class of ring graphs, a logarithmic number of
feasible solutions is required to provide a constant-factor approximation for
the LambdaPrime LP relaxation in all parameter regimes. We additionally show
that for any graph with $n$ nodes and $m$ edges, there exists a set of $m$ or
fewer clusterings such that for every $\lambda \in (0,1)$, the family contains
an exact solution to the LambdaPrime objective. There also exists a set of
$O(\log n)$ clusterings that provide a $(1+\varepsilon)$-approximate solution
in all parameter regimes; we demonstrate simple graph classes for which these
bounds are tight.

5
The categories of this paper are: gr-qc
14
The categories of this paper are: math-ph
21
The categories of this paper are: adap-org
19
The categories of this paper are: eess
27
The categories of this paper are: comp-gas
35
The categories of this paper are: mtrl-th
12
The categories of this paper are: nucl-th
13
The categories of this paper are: quant-ph
2
The categories of this paper are: math
31
The categories of this paper are: ao-sci
37
The categories of this paper are: supr-con
16
The categories of this paper are: stat
36
The categories of this paper are: cmp-lg
0
The categories of this paper are: hep-ph
20
The categories of this paper are: acc-phys
10
The categories of this paper are: q-bio