Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Maximizing Symmetric Submodular Functions   Symmetric submodular functions are an important family of submodular
functions capturing many interesting cases including cut functions of graphs
and hypergraphs. Maximization of such functions subject to various constraints
receives little attention by current research, unlike similar minimization
problems which have been widely studied. In this work, we identify a few
submodular maximization problems for which one can get a better approximation
for symmetric objectives than the state of the art approximation for general
submodular functions.
  We first consider the problem of maximizing a non-negative symmetric
submodular function $f\colon 2^\mathcal{N} \to \mathbb{R}^+$ subject to a
down-monotone solvable polytope $\mathcal{P} \subseteq [0, 1]^\mathcal{N}$. For
this problem we describe an algorithm producing a fractional solution of value
at least $0.432 \cdot f(OPT)$, where $OPT$ is the optimal integral solution.
Our second result considers the problem $\max \{f(S) : |S| = k\}$ for a
non-negative symmetric submodular function $f\colon 2^\mathcal{N} \to
\mathbb{R}^+$. For this problem, we give an approximation ratio that depends on
the value $k / |\mathcal{N}|$ and is always at least $0.432$. Our method can
also be applied to non-negative non-symmetric submodular functions, in which
case it produces $1/e - o(1)$ approximation, improving over the best known
result for this problem. For unconstrained maximization of a non-negative
symmetric submodular function we describe a deterministic linear-time
$1/2$-approximation algorithm. Finally, we give a $[1 - (1 - 1/k)^{k -
1}]$-approximation algorithm for Submodular Welfare with $k$ players having
identical non-negative submodular utility functions, and show that this is the
best possible approximation ratio for the problem.

20
The categories of this paper are: acc-phys
33
The categories of this paper are: plasm-ph
22
The categories of this paper are: chao-dyn
16
The categories of this paper are: stat
9
The categories of this paper are: nlin
34
The categories of this paper are: chem-ph
36
The categories of this paper are: cmp-lg
17
The categories of this paper are: q-fin
4
The categories of this paper are: cond-mat
12
The categories of this paper are: nucl-th
23
The categories of this paper are: solv-int
5
The categories of this paper are: gr-qc
0
The categories of this paper are: hep-ph
15
The categories of this paper are: nucl-ex
31
The categories of this paper are: ao-sci
26
The categories of this paper are: bayes-an