【摘 要】
:
Motivated by applications in wireless communications,this paper develops semidefinite programming(SDP)relaxation techniques for some mixed binary quadratically
【机 构】
:
ShanghaiUniversity
【出 处】
:
Shanghai Workshop on Numerical Algebra,Imaging and Optimizat
论文部分内容阅读
Motivated by applications in wireless communications,this paper develops semidefinite programming(SDP)relaxation techniques for some mixed binary quadratically constrained quadratic programs(MBQCQP)and analyzes their approximation performance.We consider both a minimization and a maximization model of this problem.For the minimization model,the objective is to find a minimum norm vector in $N$-dimensional real or complex Euclidean space,such that $M$ concave quadratic constraints and a cardinality constraint are satisfied with both binary and continuous variables.By employing a special randomized rounding procedure,we show that the ratio between the norm of the optimal solution of the minimization model and its SDP relaxation is upper bounded by $O(Q^2(M-Q+1)+M^2)$ in the real case and by $O(M(M-Q+1))$ in the complex case.For the maximization model,the goal is to find a maximum norm vector subject to a set of quadratic constraints and a cardinality constraint with both binary and continuous variables.We show that in this case the approximation ratio is bounded from below by $O(\epsilon∧ln(M))$ for both the real and the complex cases.Moreover,this ratio is tight up to a constant factor.
其他文献
The Projected Shell Model has been developed by including various intrinsic deformations in the configuration space.In this new method,the quadrupole deform
质子发射核为研究质子滴线附近的核结构提供了重要信息[1].1981年,在德国GSI的SHIP的速度选择器上,发现了第一个基态质子发射核151Lu.近期又发现151Lu存在一个短寿命的低自旋
I shall discuss issues related to the level surfaces and singular sets for solutions to semilinear problems of the type $Delta u = f(u)$,where $f$ admits disco
In this talk,we study some mathematical aspects on supersonic flow past a delta wing.Here the wing is assumed to be infinite along its edges,so we need only to
We survey some of our recent progress on the local well-posedness problem for compressible Navier-Stokes Equations with density dependent viscosity when initial
The Boltzmann equation can describe the gas transport phenomena for the full spectrum of flow regimes and act as the main foundation for the study of comple
In this talk,I will introduce the Wigner transport equation(WTE),which can be regarded as a quantum correction of the Boltzmann equation.The WTE has found m
We consider the Navier-Stokes Equations with Navier boundary condition.We get a strong convergence of Navier-Stokes Equations with Navier boundary condition
Time-dependent neutron transport equation is a kind of important hyperbolic partial differential equation in nuclear science and engineering applications.Hi
Kernel functions play an important role in the design and analysis of interior-point methods(IPMs).They are not only used for determining the search directions