...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Automatic Control >The real structured singular value is hardly approximable
【24h】

The real structured singular value is hardly approximable

机译：实际的结构奇异值几乎不可近似

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

摘要

This paper investigates the problem of approximating the real structured singular value (real μ). A negative result is provided which shows that the problem of checking if μ=0 is NP-hard. This result is much more negative than the known NP-hard result for the problem of checking if μ<1. One implication of our result is that μ is hardly approximable in the following sense: there does not exist an algorithm, polynomial in the size n of the μ problem, which can produce an upper bound μˉ for μ with the guarantee that μ⩽μˉ⩽K(n)μ for any K(n)>0 (even exponential functions of n), unless NP=P. A similar statement holds for the lower bound of μ. Our result strengthens a recent result by Toker, which demonstrates that obtaining a sublinear approximation for μ is NP-hard
机译：本文研究了逼近真实结​​构奇异值（真实μ）的问题。提供的否定结果表明，检查μ= 0是否存在NP-hard问题。对于检查μ<1的问题，该结果比已知的NP-hard结果负面得多。我们的结果的一个暗示是，在以下意义上，μ几乎不可近似：不存在一种算法，即μ问题大小为n的多项式，该算法可以为μ生成上限μ，并保证μ的上限。对于任何K（n）> 0（n的偶数个指数函数）的K（n）μ，除非NP = P。 μ的下界也有类似的说法。我们的结果加强了Toker的最新结果，该结果表明获得μ的亚线性近似是NP-hard

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号