Instance Specific Approximations for Unconstrained Submodular Maximization with Modular Costs

Subset selection for profit maximization is important to applications like web mining, recommendation, and machine learning, which are commonly modeled as unconstrained submodular maximization with modular costs (USM-MC) _SV f(S)-łambda c(S) where f is a nonnegative monotone submodular utility function, c is a nonnegative modular cost function and łambda is a penalty parameter. Since USM-MC is NP-hard, many existing works have developed approximation algorithms with worst-case approximation ratios. However, these approximation ratios are often too pessimistic to measure the performance of the approximate algorithms on real-world problem instances. To better evaluate the instance-specific performance of an approximate algorithm, we study data-dependent upper bounds on the optimal value, which enable an empirical approximation ratio computed as the ratio between the algorithm's solution value and the data-dependent upper bound. In this paper, we propose the Monotone Surrogate Method (MSM), a unified framework for constructing data-dependent upper bounds for USM-MC by leveraging any data-dependent upper bound developed for monotone submodular maximization with a knapsack constraint. This design makes MSM extensible and theoretically competitive. Building on the vanilla MSM upper bound, we introduce an improved upper bound as MSM+IP based on an algorithm called Iterative Prune (IP) and prove that MSM+IP is no larger than MSM. In addition, we further improve tightness using Stability Interval (SI) : when łambda changes within an SI, the IP-generated sublattice remains invariant, enabling additional tightening of MSM+IP. Experiments across eight web-based applications show that MSM+IP+SI consistently yields tighter data-dependent upper bounds than prior baselines and thus gives more informative empirical approximation ratios. The empirical approximation ratios of MSM+IP+SI are far above the classic 1/3-approximation ratio of the double greedy algorithm and are often close to 0.9, providing a more precise evaluation of solution quality than the worst-case approximation ratio.