Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming r

来源 :中国科学A辑(英文版) | 被引量 : 0次 | 上传用户:JK0803zhaozhenhong
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
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 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.
其他文献
The HIV-1 gp120 exterior envelope glycoprotein undergoes a series of conformational rearrangements while sequentially interacting with the receptor CD4 and core
Density functional theory (DFT) of quantum chemistry was used to optimize the configuration of the anionic surfactant complexes CH3(CH2)7OSO-3(H2O)n (n=0-6) and
利用Garfield气体探测器模拟程序模拟了不同条件下Micromegas探测器的增益和位置分辨特性.通过对模拟结果的分析,得出提高探测器位置分辨和增益的有效途径.该工作不仅可以优
This paper investigates the semi-online scheduling problem with the known largest size on two uniform machines. The objective is to maximize the minimum machine
The multi-category classification algorithms play an important role in both theory and practice of machine learning.In this paper,we consider an approach to the
为探究吕家坨井田地质构造格局,根据钻孔勘探资料,采用分形理论和趋势面分析方法,研究了井田7
研究了边界能量为1-10MeV的高能X射线成像系统中采用双能成像法识别物质问题.通过研究其物理机理,提出了一个近似线性的数学模型;定义了物质识别灵敏度用于评价物质识别效果;
In this paper we prove that every planar graph without 4,6 and 8-cycles is 3-colorable.
This paper investigates the Lipschitz equivalence of generalized {1,3,5}-{1,4,5} self-similar sets D = (r1D) ∪ (r2D + (1 + r1 - r2 - r3)/2) ∪ (r3D + 1 - r3) a
Let (∈n)≥0 be the Markov chain of two states with respect to the probability measure of the maximal entropy on the subshift space ∑A defined by Fibonacci inc