• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>The 8th international conference on optimization: Techniques and Applications >A polynomial case of cardinality constrained quadratic optimization problem
【24h】

A polynomial case of cardinality constrained quadratic optimization problem

机译：基数约束二次优化问题的多项式情况

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We investigate in this paper a fixed parameter polynomial algorithm for cardinality constrained quadratic optimization problem, which is NP-hard in general. More specifically, we prove that, given a problem of size n, the number of decision variables, and s, the cardinality, if, for some 0＜k ≤ n, the n - k largest eigenvalues of the coefficient matrix of the problem are identical, we can construct a solution algorithm with computational complexity of (O)(n2k), which is independent of the cardinality s. Our main idea is to decompose the primary problem into several convex subproblems, while the total number of the subproblems is determined by the number of cells generated by a corresponding hyperplane arrangement in (R)k space.
机译：我们研究了一种用于基数约束二次优化问题的固定参数多项式算法，该算法通常为NP-hard。更具体地说，我们证明，给定大小为n的问题，决策变量的数目为s，为基数，如果对于0 ＜k≤n，问题系数矩阵的n-k个最大特征值为同样，我们可以构造一个求解算法，其计算复杂度为（O）（n2k），而与基数s无关。我们的主要思想是将主要问题分解为几个凸子问题，而子问题的总数由（R）k空间中相应超平面排列生成的像元数确定。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号