首页    期刊浏览 2024年08月31日 星期六
登录注册

文章基本信息

  • 标题:Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces
  • 本地全文:下载
  • 作者:Markus Bläser ; Gorav Jindal ; Anurag Pandey
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2016
  • 卷号:2016
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We consider the problem of commutative rank computation of a given matrix space, F n n . The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is n , subsumes problems such as testing perfect matching in graphs and identity testing of algebraic branching programs. An efficient deterministic computation of the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic 2 1 -approximation algorithm for the computation of the commutative rank. This leads to a natural question of whether this approximation ratio can be improved. In this paper, we answer this question affirmatively.

    We present a deterministic PTAS for computing the commutative rank of a given matrix space. More specifically, given a matrix space F n n and a rational number 0"> 0 , we give an algorithm, that runs in time O ( n 4+ 3 ) and computes a matrix A such that the rank of A is at least (1 − ) times the commutative rank of . The algorithm is the natural greedy algorithm. It always takes the first set of k matrices that will increase the rank of the matrix constructed so far until it does not find any improvement, where the size of the set k depends on .

国家哲学社会科学文献中心版权所有