Detecting matrices of combinatorial rank three

The smallest integer k for which the elements of a real matrix A   can be expressed as Aij=mint=1k{Bit+Ctj} with B∈Rm×kB∈Rm×k and C∈Rk×nC∈Rk×n 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≤2k≤2, and we construct an algorithm that decides whether or not a given matrix has combinatorial rank three in time O((m+n)3mnlog(mn))O((m+n)3mnlog(mn)).