• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>ACM symposium on theory of computing >Efficient Rounding for the Noncommutative Grothendieck Inequality
【24h】

Efficient Rounding for the Noncommutative Grothendieck Inequality

机译：非可交换格洛腾迪克不等式的有效舍入

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a constant-factor polynomial time approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principle component analysis and the orthogonal Procrustes problem.
机译：经典的Grothendieck不等式可用于NP困难优化问题的近似算法的设计。我们表明，由于Pisier和Haagerup，Grothendieck不等式的非可交换概括也可以给出算法解释。我们的主要结果是，针对该不等式的有效舍入过程，导致针对优化问题的常数因子多项式时间逼近算法，该算法将Frieze和Kannan的Cut Norm问题推广了一般性，并在此处显示了对鲁棒主成分分析的其他应用和正交的Procrustes问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号