Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Approximation algorithms for the vertex happiness   We investigate the maximum happy vertices (MHV) problem and its complement,
the minimum unhappy vertices (MUHV) problem. We first show that the MHV and
MUHV problems are a special case of the supermodular and submodular
multi-labeling (Sup-ML and Sub-ML) problems, respectively, by re-writing the
objective functions as set functions. The convex relaxation on the Lov\'{a}sz
extension, originally presented for the submodular multi-partitioning (Sub-MP)
problem, can be extended for the Sub-ML problem, thereby proving that the
Sub-ML (Sup-ML, respectively) can be approximated within a factor of $2 -
\frac{2}{k}$ ($\frac{2}{k}$, respectively). These general results imply that
the MHV and the MUHV problems can also be approximated within $\frac{2}{k}$ and
$2 - \frac{2}{k}$, respectively, using the same approximation algorithms. For
MHV, this $\frac{2}{k}$-approximation algorithm improves the previous best
approximation ratio $\max \{\frac{1}{k}, \frac{1}{\Delta + 1}\}$, where
$\Delta$ is the maximum vertex degree of the input graph. We also show that an
existing LP relaxation is the same as the concave relaxation on the Lov\'{a}sz
extension for the Sup-ML problem; we then prove an upper bound of $\frac{2}{k}$
on the integrality gap of the LP relaxation. These suggest that the
$\frac{2}{k}$-approximation algorithm is the best possible based on the LP
relaxation. For MUHV, we formulate a novel LP relaxation and prove that it is
the same as the convex relaxation on the Lov\'{a}sz extension for the Sub-ML
problem; we then show a lower bound of $2 - \frac{2}{k}$ on the integrality gap
of the LP relaxation. Similarly, these suggest that the $(2 -
\frac{2}{k})$-approximation algorithm is the best possible based on the LP
relaxation. Lastly, we prove that this $(2 - \frac{2}{k})$-approximation is
optimal for the MUHV problem, assuming the Unique Games Conjecture.

17
The categories of this paper are: q-fin
15
The categories of this paper are: nucl-ex
28
The categories of this paper are: alg-geom
10
The categories of this paper are: q-bio
12
The categories of this paper are: nucl-th
16
The categories of this paper are: stat
31
The categories of this paper are: ao-sci
27
The categories of this paper are: comp-gas
18
The categories of this paper are: econ
2
The categories of this paper are: math
5
The categories of this paper are: gr-qc
20
The categories of this paper are: acc-phys
29
The categories of this paper are: funct-an
23
The categories of this paper are: solv-int
22
The categories of this paper are: chao-dyn
30
The categories of this paper are: q-alg