An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale

Thank you for your comments and pointing out that our algorithm outperforms existing methods in terms of running time.

The query complexity of O(nBk) appears suboptimal since B approaches n, potentially resulting in quadratic complexity. This does not seem sufficiently efficient for practical applications. The authors should consider developing an approximation with near-linear complexity, which would be more meaningful and applicable in practice.

While the proposed algorithm is faster than existing methods, its time complexity remains suboptimal for handling the massive data sets encountered in real-world applications.

A running time of $O(nB)$ is natural for the greedy algorithm which is a standard algorithm in practice and is widely applied on huge datasets. A running time of $O(nBk)$ is therefore quite natural on $k$ objectives. Even in the case where $B=\Omega(n)$, our algorithm still has significantly better running time than all prior works that offer the same approximation guarantee (Chekuri et al. ‘10, the $1-1/e$ algorithm of Udwani ‘18, Tsang et al. ‘19).

As shown in our experiments, our algorithm is vastly more performant than prior work with theoretical guarantees. We are the first to provide an algorithm that scales to ten thousands of nodes (and potentially more; the running time of our algorithm on the largest instances we tried is not yet prohibitive) while providing the best possible approximation ratio.

However, its runtime is inferior compared to the other two greedy-based algorithms, namely Greedy Minimum and Greedy Round Robin. Additionally, the datasets used in the paper are relatively small, making it difficult to evaluate the efficiency of the algorithms in real-world large-scale environments.

As compared to greedy, our algorithm has theoretical guarantees. We outperform all algorithms with comparable theoretical guarantees in terms of running time, which form a long line of work that improves upon the objective value of the greedy algorithm.

The biggest instance in our experiments has $n=10378$ elements which is substantially larger than any of the instances used in the literature on multiobjective submodular maximization with theoretical guarantees (before us, the largest instance appears in Udwani ‘2018 with $n=1024$ elements).

However, some important works in this area have been overlooked, such as [1][2]. [1] Fazzone, A., Wang, Y., & Bonchi, F. (2024). Fair Representation in Submodular Subset Selection: A Pareto Optimization Approach. Transactions on Machine Learning Research. [2] Cui, Shuang, et al. "Fairness in streaming submodular maximization subject to a knapsack constraint." Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.

We will cite these papers in our related work along the following discussion:

• [1] solves a multi-objective problem by extending the saturate algorithm to obtain a sequence of approximately pareto-optimal solutions, while our algorithm gives a single solution for the (max-min) multiobjective problem.
• [2] considers a fairness notion that enforces constraints on the solution set. (We will add [2] alongside similar works that we cite in our related work section (e.g., Celis et al. ‘18)).

Thank you for evaluation and the positive comments on our writing and the scalability of our approach.

The technical novelty of the work seems marginal. While the proposed solution outperforms existing studies in terms of lower running time and improved approximation ratio, the fundamental design and analysis of the algorithm appear to be inspired by previous work, such as Chekuri et al. (2010). Moreover, the results of Chekuri et al. (2010) can be applied to a broader range of constraints, such as matroid constraints. Additionally, I believe their results do not rely on the budget constraint $B$.

Our method and swap rounding (due to Chekuri et al. (2010) and also used in later works, e.g. in Tsang et al. (2019)) are different approaches towards the multiobjective problem. The idea of swap rounding is to build a fractional solution (which they find using gradient ascent over the multilinear extension) and in the last step round it to a discrete solution. Our method adds one (discrete) element in each iteration. This leads to important differences in both the running time and the analysis of both approaches. Since we do not optimize over the multilinear extension, our approach is decisively faster: We only need $O(nBk)$ function evaluations compared to exponentially many queries (and exponential runtime) of Chekuri et al. (2010). We also carry out a different martingale analysis that is tailored to the greedy algorithm. Furthermore, their algorithm also depends on $B$ to establish their approximation guarantee, which is natural for the multiobjective problem to avoid the inapproximability regime ($B<k$) shown by Krause et al. (2008). Another natural reason for a dependence on the budget in swap rounding is that the Chernoff bound obtains better concentration for larger budgets, even for linear functions.

The paper lacks a direct comparison between their method and the one proposed in Chekuri et al. (2010) in the experimental section. While I understand that Chekuri et al. (2010)’s algorithm may not be practical due to its reliance on multilinear extensions, I would have appreciated seeing some comparative results in a small- or medium-scale setting to better understand the trade-offs.

We compare our paper with the approach of Tsang et al. (2019) which provides a practical implementation of the approach of Chekuri et al. (2010) by performing gradient ascent efficiently via Frank-Wolfe. Their parameters are chosen to make the algorithm practical on special medium-sized instances (their algorithm does not apply to general applications such as fair centrality maximization, which is why we exclude it there). However, their algorithm is still slower and has worse objective value than our algorithm, suggesting that the trade-offs of the unrefined approach of Chekuri et al. (2010) are also poor.

Thank you for your comments and the positive feedback on our presentation.

However, it seems a greedy heuristics algorithm finds almost the same submodular value, while having better running time and query complexity.

The only weakness is that the greedy minimum algorithm seems to outperform their algorithm in experiments but since that one does not have an approximation guarantee, still their algorithm and its analysis remain interesting.

While the greedy heuristic does obtain high objective value, there is a long line of work on the multiobjective problem which aims to improve upon greedy heuristics (Leskovec et al. ‘10; Chekuri et al. ‘10; Orlin et al. ‘18; Udwani ‘18; Tsang et al. ‘19). We contribute to this line of work by providing the first practical algorithm with the best possible approximation guarantee. Although greedy might perform similarly in practice it does not have any theoretical guarantees, as the reviewer points out. Such guarantees are valuable as they ensure that we consistently perform well on any given instance. In particular, we outperform or match greedy in objective value.

Thank you for your evaluation and the encouraging comments on the strengths of our paper.

This work isn't essential, but I would appreciate a discussion of [1], as elaborated in strengths and weaknesses. [1]. Buchbinder, Niv, et al. "Submodular maximization with cardinality constraints." Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014. I do think it would be a good idea to cite [1] and explain the relationship between the algorithms. Would like to see [1] cited and a discussion of the relationship between the combinatorial algorithm (RandomGreedy) in that paper and this one. Could ideas from RandomGreedy (which works for non-monotone objective) extend to a non-monotone variant of the algorithm in this paper?

A similarity is that we sample randomly, but our sampling probabilities are carefully chosen to solve the multiobjective problem. One way to see the difference between the algorithms (in terms of the goal and design of either algorithm) is if we run our algorithm for only a single color. Then our algorithm reduces to greedy, showing that our sampling is designed only to enforce good progress across all colors. Their sampling is (intuitively) intended to avoid adding “bad elements” to the solution. However, we believe it could be a promising idea to combine both sampling strategies to obtain an algorithm for non-monotone multiobjective maximization. We will add such a discussion to our paper.

line 107: seting -> setting It might be a good idea if B > k, or the approximability of the problem were discussed earlier. When reading Problem 3.1, I was wondering about this. If B < k, clearly inapproximable.

In a revised version, we will fix the typo and state after Problem 3.1 that we are interested in the case where the budget is large compared to k ($B>k$).

Is there a direction transformation from the notion of fairness as a constraint (as in some of the references discussed in the introduction) to the multi-objective notion of fairness? If so, how do the results in those papers compare with this one?

Fairness as a constraint is enforced on the solution set itself. For instance, one can require that the intersection of the solution set with each group (groups are subsets of the ground set) has a certain size. The multiobjective problem is different in that it asks for fairness in the objectives, which corresponds to the notion of max-min fairness on the outcomes. As such, we do not think that one problem can be cast as the other.