Optimization and optimality test for the Max-Cut Problem |
| |
| Authors: | Chr Hohmann Dr. W. Kern |
| |
| Affiliation: | 1. Dept. of Applied Mathematics, University of Twente, Postbus 217, NL-7500, AE Enschede
|
| |
| Abstract: | We show that the following two problems are polynomially equivalent:| 1) | Given a (weighted) graphG, and a cutC ofG, decide whetherC is maximal or not. | | 2) | Given a (weighted) graphG, and a cutC ofG, decide whetherC is maximal or not, and in case it is not, find a better solutionC . |
As a consequence, an optimality testing oracle may be used to design a polynomial time algorithm for approximately solving the (weighted) Max-Cut Problem. |
| |
| Keywords: | Max-cut decision problem optimization problem polynomial transformation |
| 本文献已被 SpringerLink 等数据库收录！ |
|
