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. $$

I would appreciate any input!

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!