论文标题
用于无约束二进制二进制优化的多项式时间算法
A Polynomial-Time Algorithm for Unconstrained Binary Quadratic Optimization
论文作者
论文摘要
在本文中，开发了多项式时间中的精确算法来解决无限制的二进制二次程序。计算复杂度为$ o \ left（n^{\ frac {15} {2}}} \ right）$，尽管非常保守，但足以证明这个最小化问题在复杂性类别$ p $中。还详细描述了实施方面，特别强调了二次程序转换为线性程序，该程序可以在多项式时间内解决。该算法是在MATLAB中实现的，并通过生成500万个任意尺寸的矩阵，最多30个，随机条目在$ \ weft [-50,50 \右] $中。进行的所有实验都表明该方法可以正常工作。
In this paper, an exact algorithm in polynomial time is developed to solve unrestricted binary quadratic programs. The computational complexity is $O\left( n^{\frac{15}{2}}\right) $, although very conservative, it is sufficient to prove that this minimization problem is in the complexity class $P$. The implementation aspects are also described in detail with a special emphasis on the transformation of the quadratic program into a linear program that can be solved in polynomial time. The algorithm was implemented in MATLAB and checked by generating five million matrices of arbitrary dimensions up to 30 with random entries in the range $\left[ -50,50\right] $. All the experiments carried out have revealed that the method works correctly.
