Optimization and optimality test for the Max-Cut Problem

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.


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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr86-035
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 09 Jan 2012 11:49
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/35