Before revision:  We finally boost this algorithmto a (1-1/e-\epsilon) randomized algorithm for the general case, thus matching the result of Fairstein et al. 13 .
After revision:  We finally boost this algorithmto a (1-1/e-\epsilon) randomized algorithm for the general case, thus matching the result of Fairstein et al. deterministic algorithm for SMKP. Our algorithm is based on reducing SMKP to an exponential-size submodular maximizaion problem over a special partition matroid which enjoys a tight deterministic algorithm. We develop several techniques to mimic the algorithm, leading to a tight deterministic approximation for SMKP .