...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity _2O(n log n)
【24h】

A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity _2O(n log n)

机译：复杂度为_2O（n log n）的拟凸多项式整数最小化的新Lenstra型算法

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

摘要

We study the integer minimization of a quasiconvex polynomial with quasiconvex polynomial constraints. We propose a new algorithm that is an improvement upon the best known algorithm due to Heinz [S. Heinz, Complexity of integer quasiconvex polynomial optimization, Journal of Complexity 21(4) (2005) 543-556]. This improvement is achieved by applying a new modern Lenstra-type algorithm, finding optimal ellipsoid roundings, and considering sparse encodings of polynomials. For the bounded case, our algorithm attains a time-complexity of s(rlMd) ~(O(1))2~2nlog_2(n)+O(n) when M is a bound on the number of monomials in each polynomial and r is the binary encoding length of a bound on the feasible region. In the general case, sl ~(O(1))d~(O(n))2~2nlog_2(n)+O(n). In each we assume d≥2 is a bound on the total degree of the polynomials and l bounds the maximum binary encoding size of the input.
机译：我们研究了具有拟凸多项式约束的拟凸多项式的整数最小化。我们提出了一种新算法，该算法是对因亨氏[S. Heinz，整数拟凸多项式优化的复杂度，Journal of Complexity 21（4）（2005）543-556]。通过应用新的现代Lenstra型算法，找到最佳椭球舍入并考虑多项式的稀疏编码，可以实现这一改进。对于有界情况，当M是每个多项式和r的单项式数的有界时，我们的算法获得s（rlMd）〜（O（1））2〜2nlog_2（n）+ O（n）的时间复杂度是可行区域上边界的二进制编码长度。在一般情况下，sl〜（O（1））d〜（O（n））2〜2nlog_2（n）+ O（n）。在每种情况下，我们假设d≥2是多项式总和的界，而l则约束输入的最大二进制编码大小。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号