Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Approximation Algorithms For The Dispersion Problems in a Metric Space   In this article, we consider the $c$-dispersion problem in a metric space
$(X,d)$. Let $P=\{p_{1}, p_{2}, \ldots, p_{n}\}$ be a set of $n$ points in a
metric space $(X,d)$. For each point $p \in P$ and $S \subseteq P$, we define
$cost_{c}(p,S)$ as the sum of distances from $p$ to the nearest $c $ points in
$S \setminus \{p\}$, where $c\geq 1$ is a fixed integer. We define
$cost_{c}(S)=\min_{p \in S}\{cost_{c}(p,S)\}$ for $S \subseteq P$. In the
$c$-dispersion problem, a set $P$ of $n$ points in a metric space $(X,d)$ and a
positive integer $k \in [c+1,n]$ are given. The objective is to find a subset
$S\subseteq P$ of size $k$ such that $cost_{c}(S)$ is maximized. We propose a
simple polynomial time greedy algorithm that produces a $2c$-factor
approximation result for the $c$-dispersion problem in a metric space. The best
known result for the $c$-dispersion problem in the Euclidean metric space
$(X,d)$ is $2c^2$, where $P \subseteq \mathbb{R}^2$ and the distance function
is Euclidean distance [ Amano, K. and Nakano, S. I., Away from Rivals, CCCG,
pp.68-71, 2018 ]. We also prove that the $c$-dispersion problem in a metric
space is $W[1]$-hard.

17
The categories of this paper are: q-fin
13
The categories of this paper are: quant-ph
3
The categories of this paper are: physics
37
The categories of this paper are: supr-con
35
The categories of this paper are: mtrl-th
34
The categories of this paper are: chem-ph
15
The categories of this paper are: nucl-ex
7
The categories of this paper are: hep-th
12
The categories of this paper are: nucl-th
10
The categories of this paper are: q-bio
11
The categories of this paper are: hep-lat
24
The categories of this paper are: dg-ga
9
The categories of this paper are: nlin
18
The categories of this paper are: econ
0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom