Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation |
| |
Authors: | Da-chuan Xu Shu-zhong Zhang |
| |
Affiliation: | 1. Department of Applied Mathematics,Beijing University of Technology,Beijing 100022,China 2. Department of Systems Engineering and Engineering Management,The Chinese University of Hong Kong,Shatin,Hong Kong,China |
| |
Abstract: | In this paper, we consider a class of quadratic maximization problems. For a subclass of the problems, we show that the SDP relaxation approach yields an approximation solution with the worst-case performance ratio at least α = 0.87856 ⋯. In fact, the estimated worst-case performance ratio is dependent on the data of the problem with α being a uniform lower bound. In light of this new bound, we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at least α + δ d if every weight is strictly positive, where δ d > 0 is a constant depending on the problem dimension and data. This work was supported by the National Natural Science Foundation of China (Grant No. 10401038) and Startup Grant for Doctoral Research of Beijing University of Technology and Hong Kong RGC Earmarked Grant CUHK4242/04E |
| |
Keywords: | quadratic maximization max-cut problem semidefinite programming relaxation approximation algorithm performance ratio |
本文献已被 万方数据 SpringerLink 等数据库收录! |
|