Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Max-Sum Diversification, Monotone Submodular Functions and Dynamic
  Updates   Result diversification is an important aspect in web-based search, document
summarization, facility location, portfolio management and other applications.
Given a set of ranked results for a set of objects (e.g. web documents,
facilities, etc.) with a distance between any pair, the goal is to select a
subset $S$ satisfying the following three criteria: (a) the subset $S$
satisfies some constraint (e.g. bounded cardinality); (b) the subset contains
results of high "quality"; and (c) the subset contains results that are
"diverse" relative to the distance measure. The goal of result diversification
is to produce a diversified subset while maintaining high quality as much as
possible. We study a broad class of problems where the distances are a metric,
where the constraint is given by independence in a matroid, where quality is
determined by a monotone submodular function, and diversity is defined as the
sum of distances between objects in $S$. Our problem is a generalization of the
{\em max sum diversification} problem studied in \cite{GoSh09} which in turn is
a generaliztion of the {\em max sum $p$-dispersion problem} studied extensively
in location theory. It is NP-hard even with the triangle inequality. We propose
two simple and natural algorithms: a greedy algorithm for a cardinality
constraint and a local search algorithm for an arbitary matroid constraint. We
prove that both algorithms achieve constant approximation ratios.

22
The categories of this paper are: chao-dyn
28
The categories of this paper are: alg-geom
37
The categories of this paper are: supr-con
15
The categories of this paper are: nucl-ex
10
The categories of this paper are: q-bio
33
The categories of this paper are: plasm-ph
4
The categories of this paper are: cond-mat
21
The categories of this paper are: adap-org
25
The categories of this paper are: patt-sol
16
The categories of this paper are: stat
3
The categories of this paper are: physics
9
The categories of this paper are: nlin
12
The categories of this paper are: nucl-th
27
The categories of this paper are: comp-gas
26
The categories of this paper are: bayes-an
5
The categories of this paper are: gr-qc