Hohmann, C. and Kern, Walter (1990) Optimization and optimality test for the Max-Cut Problem.
Published in: Zeitschrift für Operations-Research : ZOR ; mathematical methods of operations research Vol. 34 (3). pp. 195-206.

Abstract

The authors show that, for the weighted and unweighted version of the max-cut problem, there is a polynomial equivalent optimality test which improves a given suboptimal solution. For the weighted case, the proof uses rescaling techniques (for a given cut, the graph is modified by scaling the weight of the uncut edges by a factor 0 < lambda < 1) together with concurrent uses of an optimal testing oracle and binary search. As a corollary one gets, with the help of an optimality testing oracle, a polynomial-time heuristic for the weighted max-cut problem. For the unweighted case, the proof is much simpler, and the heuristic is now an exact algorithm. This implies that recognizing an optimal cut in an unweighted graph is NP-hard.

Actions:

Full text not available from this repository.

Editorial actions:	View Item (Login required)