English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $V$ be a set of $n$ vertices, ${\cal M}$ a set of $m$ labels, and let$\mathbf{R}$ be an $m \times n$ matrix of independent Bernoulli randomvariables with success probability $p$. A random instance$G(V,E,\mathbf{R}^T\mathbf{R})$ of the weighted random intersection graph modelis constructed by drawing an edge with weight $[\mathbf{R}^T\mathbf{R}]_{v,u}$between any two vertices $u,v$ for which this weight is larger than 0. In thispaper we study the average case analysis of Weighted Max Cut, assuming theinput is a weighted random intersection graph, i.e. given$G(V,E,\mathbf{R}^T\mathbf{R})$ we wish to find a partition of $V$ into twosets so that the total weight of the edges having one endpoint in each set ismaximized. We initially prove concentration of the weight of a maximum cut of$G(V,E,\mathbf{R}^T\mathbf{R})$ around its expected value, and then show that,when the number of labels is much smaller than the number of vertices, a randompartition of the vertices achieves asymptotically optimal cut weight with highprobability (whp). Furthermore, in the case $n=m$ and constant average degree,we show that whp, a majority type algorithm outputs a cut with weight that islarger than the weight of a random cut by a multiplicative constant strictlylarger than 1. Then, we highlight a connection between the computationalproblem of finding a weighted maximum cut in $G(V,E,\mathbf{R}^T\mathbf{R})$and the problem of finding a 2-coloring with minimum discrepancy for a setsystem $\Sigma$ with incidence matrix $\mathbf{R}$. We exploit this connectionby proposing a (weak) bipartization algorithm for the case $m=n,p=\frac{\Theta(1)}{n}$ that, when it terminates, its output can be used to finda 2-coloring with minimum discrepancy in $\Sigma$. Finally, we prove that, whpthis 2-coloring corresponds to a bipartition with maximum cut-weight in$G(V,E,\mathbf{R}^T\mathbf{R})$.

MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems