The aim has been to minimize regression test suites while retaining fault detection capability of the test suite admissible. An appropriate minimized test suite should exercise different execution paths within a program. However, minimization of test suites may result in significant fault detection loss. To alleviate the loss, a new bi-criteria heuristic algorithm, using cluster analysis of test cases execution profiles is proposed in this paper. Cluster analysis of execution profiles categorizes test cases according to their similarity in terms of exercising a certain coverage criterion. Considering additional coverage criteria the proposed algorithm samples some test cases from each cluster. These additional criteria exercise execution paths, different from those covered by the main testing criteria. Experiments on the Siemens suite manifest the applicability of the proposed approach and present interesting insights into the use of cluster analysis to the bi-criteria test suite reduction.