• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Global Optimization >A polynomial case of the cardinality-constrained quadratic optimization problem
【24h】

A polynomial case of the cardinality-constrained quadratic optimization problem

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

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

摘要

We propose in this paper a fixed parameter polynomial algorithm for the 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 the n - k largest eigenvalues of the coefficient matrix of the problem are identical for some 0 < k ≤ n, we can construct a solution algorithm with computational complexity of O (n~(2k)). Note that this computational complexity is independent of the cardinality s and is achieved by decomposing the primary problem into several convex subproblems, where the total number of the subproblems is determined by the cell enumeration algorithm for hyperplane arrangement in R~k space.
机译：我们针对基数约束的二次优化问题提出了一种固定参数多项式算法，该算法通常为NP-hard。更具体地说，我们证明，给定大小为n（决策变量的数量）和s（基数）的问题，如果问题的系数矩阵的n-k个最大特征值在0

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号