Matrix clustering is a technique which permutes rows and columns of a matrix to form densely packed regions. It originated in the 70's and initially was used for various object grouping problems, such as machine-component grouping. The database community noticed these algorithms and successfully applied them to the vertical partitioning problem. Recently, there has been a resurgence of interest in these algorithms. Nowadays, they are being considered for dynamic (on-line) vertical partitioning and tuning of multistores. In our previous papers we have described our project aimed at studing the applicability of recent matrix clustering algorithms for the vertical partitioning problem. We have presented our evaluation approach and reported results concerning several of these algorithms. Our idea was to evaluate them directly using the PostgreSQL database. Previous studies have found that these algorithms can be of use if they employ the attribute replication strategy. In this paper, we continue our investigation and consider a novel algorithm of this class. Its distinctive feature is that it performs attribute replication during the branch and bound search. We compare it with the best one of the earlier algorithms using both real and synthetic workloads. Our experiments have demonstrated that the novel algorithm produces slightly worse configurations (about 10%), but its run times are significantly better and are almost independent of the cohesion parameter.