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