Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Greedy MAXCUT Algorithms and their Information Content   MAXCUT defines a classical NP-hard problem for graph partitioning and it
serves as a typical case of the symmetric non-monotone Unconstrained Submodular
Maximization (USM) problem. Applications of MAXCUT are abundant in machine
learning, computer vision and statistical physics. Greedy algorithms to
approximately solve MAXCUT rely on greedy vertex labelling or on an edge
contraction strategy. These algorithms have been studied by measuring their
approximation ratios in the worst case setting but very little is known to
characterize their robustness to noise contaminations of the input data in the
average case. Adapting the framework of Approximation Set Coding, we present a
method to exactly measure the cardinality of the algorithmic approximation sets
of five greedy MAXCUT algorithms. Their information contents are explored for
graph instances generated by two different noise models: the edge reversal
model and Gaussian edge weights model. The results provide insights into the
robustness of different greedy heuristics and techniques for MAXCUT, which can
be used for algorithm design of general USM problems.

32
The categories of this paper are: atom-ph
0
The categories of this paper are: hep-ph
23
The categories of this paper are: solv-int
15
The categories of this paper are: nucl-ex
33
The categories of this paper are: plasm-ph
10
The categories of this paper are: q-bio
36
The categories of this paper are: cmp-lg
25
The categories of this paper are: patt-sol
35
The categories of this paper are: mtrl-th
18
The categories of this paper are: econ
20
The categories of this paper are: acc-phys
27
The categories of this paper are: comp-gas
14
The categories of this paper are: math-ph
22
The categories of this paper are: chao-dyn
16
The categories of this paper are: stat
8
The categories of this paper are: hep-ex