• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Detecting matrices of combinatorial rank three

Journal of Combinatorial Theory, Series A. 2014. Vol. 126. P. 166-176.

The smallest integer k for which the elements of a real matrix A can be expressed as A_ij = min B_it + C_tj with B an m-by-k matrix and C an k-by-n matrix is called the combinatorial rank of A. This notion was introduced by Barvinok in 1993, and he posed a problem on the complexity of detecting matrices with combinatorial rank equal to a fixed integer k. Fast algorithms solving this problem have been known only for k=2, and we construct an algorithm that decides whether or not a given matrix has combinatorial rank three in time O((m + n)^3 mn log(mn)).