Multiobjective Submodular Maximization with Concave Aggregation

Multiobjective submodular maximization asks for a single set that performs well across multiple submodular objectives, a setting motivated by robust experimental design and fairness-aware decision making. The standard max-min formulation, however, can be overly conservative: it is determined entirely by the worst-performing objective and ignores improvements in the remaining objectives unless they change the minimum. Motivated by concave social-welfare aggregators from economics, we initiate the study of multiobjective submodular maximization with general concave aggregation. We propose a randomized greedy algorithm that, in each iteration, computes a distribution over elements by solving a concave program and samples an element from this distribution. Our analysis overcomes the loss of the objective-wise decomposition available in the max-min case and proves an asymptotic $(1-1/e-ϵ)$-approximation under mild concentration assumptions. To make the method scalable, we develop a Fenchel-duality-based lazy evaluation scheme. Experiments on synthetic and real-world instances show that our algorithm consistently improves over a naive greedy baseline across a variety of concave aggregators, while enabling utility–fairness trade-offs that are not captured by the max-min formulation.