Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Understanding the Correlation Gap for Matchings   Given a set of vertices $V$ with $|V| = n$, a weight vector $w \in
(\mathbb{R}^+ \cup \{ 0 \})^{\binom{V}{2}}$, and a probability vector $x \in
[0, 1]^{\binom{V}{2}}$ in the matching polytope, we study the quantity
$\frac{E_{G}[ \nu_w(G)]}{\sum_{(u, v) \in \binom{V}{2}} w_{u, v} x_{u, v}}$
where $G$ is a random graph where each edge $e$ with weight $w_e$ appears with
probability $x_e$ independently, and let $\nu_w(G)$ denotes the weight of the
maximum matching of $G$. This quantity is closely related to correlation gap
and contention resolution schemes, which are important tools in the design of
approximation algorithms, algorithmic game theory, and stochastic optimization.
  We provide lower bounds for the above quantity for general and bipartite
graphs, and for weighted and unweighted settings. he best known upper bound is
$0.54$ by Karp and Sipser, and the best lower bound is $0.4$. We show that it
is at least $0.47$ for unweighted bipartite graphs, at least $0.45$ for
weighted bipartite graphs, and at lea st $0.43$ for weighted general graphs. To
achieve our results, we construct local distribution schemes on the dual which
may be of independent interest.

27
The categories of this paper are: comp-gas
11
The categories of this paper are: hep-lat
37
The categories of this paper are: supr-con
25
The categories of this paper are: patt-sol
34
The categories of this paper are: chem-ph
12
The categories of this paper are: nucl-th
26
The categories of this paper are: bayes-an
14
The categories of this paper are: math-ph
10
The categories of this paper are: q-bio
35
The categories of this paper are: mtrl-th
9
The categories of this paper are: nlin
2
The categories of this paper are: math
36
The categories of this paper are: cmp-lg
22
The categories of this paper are: chao-dyn
21
The categories of this paper are: adap-org
32
The categories of this paper are: atom-ph