We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as max|A|=kmini∈{1,…,m}fi(A). While it is widely known that greedy methods work well for a single objective, the problem becomes much harder with multiple objectives. In fact, Krause et al.\ (2008) showed that when the number of objectives m grows as the cardinality k i.e., m=Ω(k), the problem is inapproximable (unless P=NP). We focus on the case where the number of objectives is super-constant yet much smaller than the cardinality of the chosen set. We propose the first constant factor algorithms for this regime, including one with the best achievable asymptotic guarantee and also a more practical nearly linear time algorithm. Experiments on synthetic data show that a heuristic based on our more practical and fast algorithm outperforms existing heuristics.