Attribute reduction is one of the most important topics in rough set theory. In the classical rough sets, the method for attribute reduction is mainly to keep positive region, boundary region, and negative region unchanged. However, the three regions are no longer monotonic with respect to adding or deleting an attribute in decision-theoretic rough sets. In decision-theoretic rough set model, the decision regions are determined by using the Bayesian decision procedure, and decision-making should take consideration of the cost. In this paper, two attribute reduction methods based on minimum decision cost are proposed from the algebraic view and the information theory, respectively. First, significance of joint attributes is introduced to measure the classification ability of selected attribute subset to decision-making, which overcomes the disadvantage of only considering the significance of single attribute. By using significance of joint attributes, a heuristic method based on minimum decision cost for attribute reduction is presented. Second, conditional mutual information is proposed to evaluate the significance of attribute subset for decision-making in minimum cost attribute reduction. To decrease the computational complexity of the conditional mutual information, an approximate computation method is calculated from both maximum relevance and maximum significance. To evaluate the two proposed algorithms, extensive experiments are conducted on 10 University of California at Irvine data sets. We compare our proposed algorithms with several existing cost minimization attribute reduction algorithms. Experiment results show that our proposed algorithms have a superior performance in achieving the reduct. Copyright © 2016 John Wiley & Sons, Ltd.