Lower Bounds for Maximum Weighted Cut

Gregory Gutin, Anders Yeo

While there have been many results on lower bounds for Max Cut in unweighted graphs, there are only few results for lower bounds for Max Cut in weighted graphs. In this paper, we l…