Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) cuts of this graph, which one has the minimum weight? More concretely,
$$
\min_{\sigma\in\{-1,1\}^n}\sum_{1\leq i <j\leq n, \sigma_i\neq \sigma_j}W_{ij} = \max_{\sigma\in\{-1,1\}^n}\sum_{1\leq i<j\leq n,\sigma_i=\sigma_j}W_{ij}.
$$
How can we characterize such a minimum (maximum)? 

My thoughts are as follows:

 1. Clearly, if $\sigma$ and $-\sigma$ have the same weights, they are in a sense equivalent.
 2. If $W_{ij}>0$ for every $i,j$, then trivially the optimum is $ \sigma=(+1,+1,\dots,+1)$ (and also, $(-1,-1,\dots,-1)$). 
 3. So, the problem starts getting interesting, when the weight distribution also has some negative support.
 4. The objective can be expressed as, say, 
$$
\max_{\sigma\in\{-1,1\}^n}\sum_{1\leq i<j\leq n,\sigma_i=\sigma_j}W_{ij}=\max_{\sigma\in\{-1,1\}^n}\sum_{1\leq i<j\leq n}W_{ij}(\sigma_i+\sigma_j)^2.
$$
 5. If $W_{ij}>0$, then assuming we do not assume a cut with $\sigma_i$ all $+1$ or $-1$, the Fulkerson-Ford algorithm finds the min-cut in polynomial time.

I would appreciate any input!