Fast Stochastic Greedy Algorithm for k k -Submodular Cover Problem

Hue T. Nguyen, Tan D. Tran, Nguyen Long Giang, Canh V. Pham (✉) · 2025

Read Fast Stochastic Greedy Algorithm for k k -Submodular Cover Problem by Hue T. Nguyen, Tan D. Tran, Nguyen Long Giang, Canh V. Pham (✉) (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00869.txt.

Introduction

Hue Nguyen and colleagues study the k-submodular cover problem, a generalization of a classic covering problem that shows up in influence maximization, resource allocation, and sensor placement. Earlier algorithms either guarantee only weak approximation quality or need far too many evaluations of the objective function.

They propose a fast stochastic greedy algorithm that samples rather than scanning everything, sharply cutting the number of function evaluations. The method keeps a strong two sided approximation guarantee, in the bicriteria sense, while running much more cheaply than the best known alternatives. For large real world artificial intelligence tasks where each evaluation is expensive, that combination of speed and guarantee is the practical point of the work.

Catalog record

CREATORHue T. Nguyen, Tan D. Tran, Nguyen Long Giang, Canh V. Pham (✉)
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-00869

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fast Stochastic Greedy Algorithm for k k -Submodular Cover Problem Hue T. Nguyen, Tan D. Tran, Nguyen Long Giang, Canh V. Pham (✉) Abstract We study the k k -Submodular Cover ( kSC ) problem, a natural generalization of the classical Submodular Cover problem that arises in artificial intelligence and combinatorial optimization tasks such as influence maximization, resource allocation, and sensor placement. Existing algorithms for kSC often provide weak approximation guarantees or incur prohibitively high query complexity. To overcome these limitations, we propose a Fast Stochastic Greedy algorithm that achieves strong bicriteria approximation while substantially lowering query complexity compared to state-of-the-art methods. Our approach dramatically reduces the number of function evaluations, making it highly scalable and practical for large-scale real-world AI applications where efficiency is essential. 1 Introduction The k -submodular optimization problems have played an important role in both operations research and artificial intelligence , with applications spanning a wide range of topics such as influence maximization with multiple topics in social networks [ 17 , 22 , 15 , 31 , 19 ] , sensor placement [ 17 , 22 , 21 , 31 ] , feature selection [ 24 ] , and information coverage maximization [ 21 , 7 ] , etc. Formally, let V be a finite ground set and k be a positive integer. We denote [k]=\{1,2,\ldots,k\} and define (k+1)^{V}=\{(V_{1},V_{2},\ldots,V_{k})\mid V_{i}\subseteq V,\ \forall i\in[k],\ V_{i}\cap V_{j}=\emptyset\ \forall i\neq j\}, which is the family of k disjoint subsets of V , called a k -set . A function f:(k+1)^{V}\mapsto\mathbb{R}_{+} is called k -submodular if, for any k - set {\textbf{x}}=(X_{1},X_{2},\ldots,X_{k}) and {\textbf{y}}=(Y_{1},Y_{2},\ldots,Y_{k}) in (k+1)^{V} , it holds that f({\textbf{x}})+f({\textbf{y}})\geq f({\textbf{x}}\sqcap{\textbf{y}})+f({\textbf{x}}\sqcup{\textbf{y}}), where {\textbf{x}}\sqcap{\textbf{y}}=(X_{1}\cap Y_{1},\ldots,X_{k}\cap Y_{k}), and {\textbf{x}}\sqcup{\textbf{y}}=(Z_{1},\ldots,Z_{k}),\quad Z_{i}=X_{i}\cup Y_{i}\setminus\bigcup_{j\neq i}(X_{j}\cup Y_{j}). In this paper, we study the k -Submodular Cover ( kSC ) problem , defined as follows: Definition 1 ( kSC problem) Given a threshold T\leq\max_{{\textbf{x}}\in(k+1)^{V}}supp({\textbf{x}}) , kSC asks to find {\textbf{x}}=(X_{1},X_{2},\ldots,X_{k})\in(k+1)^{V} with size of solution |{\textbf{x}}|=\sum_{i\in[k]}|X_{i}| so that f({\textbf{x}})\geq T . When k=1 , the kSC reduces to the well-known Submodular Cover ( \mathsf{SC} ) problem [ 1 , 6 , 5 ] . This classical setting has been applied in diverse domains, such as threshold influence propagation in social networks [ 13 , 3 ] , data summarization [ 28 , 2 ] , and revenue maximization in online social platforms [ 8 , 3 ] . For the general case with arbitrary k , kSC naturally serves as the dual formulation of the extensively studied k -Submodular Maximization subject to a knapsack constraint [ 19 , 7 , 27 ] . It provides a unified abstraction for a wide range of practical tasks where the objective is to identify a minimum budget, size, cost solution that guarantees the utility function surpasses a prescribed threshold. Specifically, kSC arises in numerous significant applications such as information diffusion and online advertising in social networks. A representative application is the k -type Product Revenue Cover . In this setting, an enterprise aims to promote products across multiple categories—such as electronics, fashion, or household items—while ensuring that the total revenue surpasses a predefined threshold T . Each customer contributes differently to the revenue depending on the product category, and each customer can be associated with at most one category. The goal is to select a subset of customers to target with promotional offers such that the aggregated revenue across all k categories exceeds T , while minimizing the overall marketing cost. This problem naturally extends the classical submodular revenue maximization models into a multi-category, k -submodular framework. Another important instance is the Influence Threshold with k -topics . In viral marketing or product recommendation, an enterprise may wish to spread an advertising campaign simultaneously over k different categories to influence at least T individuals in a social network. To reduce expenses, they engage key opinion leaders or influential users to trigger this impact with minimal cost. This setting generalizes both the standard influence diffusion model for a single topic ( k=1 ) [ 10 , 14 ] and the influence threshold formulation [ 12 ] . Beyond these, kSC also naturally arises in other important domains, such as multi-type sensor placement for guaranteed information acquisition, and multi-class feature selection in machine learning. Together, these applications illustrate the broad relevance and impact of the kSC formulation across optimization, data mining, and artificial intelligence. Although the range of applications of kSC is extensive, it is remarkable that only a handful of studies have explicitly examined this problem. Furthermore, the established results for the classical \mathsf{SC} problem are not directly transferable to kSC because of the fundamental distinctions between k -submodularity and submodularity (see [ 16 ] ). This difference also accounts for why algorithms developed for k -submodular optimization generally provide weaker approximation bounds compared to those in submodular optimization. The earliest exploration of kSC was given in [ 20 ] , where the presented algorithm achieves a bicriteria approximation that is comparatively weak in this scenario (see Table 1 for a summary). Therefore, determining whether polynomial-time approximation algorithms for kSC with tighter theoretical guarantees and practical efficiency exist remains an open research challenge. Table 1: Algorithms for kSC problem. The tuple (x,y) presents (x,y) -bicriteria approximation ratio for an algorithm, i.e, it returns a solution s such that supp({\textbf{s}})\leq y\cdot{\mathsf{opt}} and f({\textbf{s}})\geq x\cdot T , where x,y>0 . Compared to the streaming algorithm in [ 20 ] , our proposed algorithm FastSG achieves a significantly stronger bicriteria approximation ratio. In particular, by setting \delta=\epsilon^{2} , it ensures a higher bound on solution quality, i.e., |supp({\textbf{s}})|\leq(1+\epsilon)\left(1+\ln\!\left(\tfrac{1}{\delta}\right)\right) , while attaining the same utility value as the streaming approach, namely f({\textbf{s}})\geq\tfrac{1-\epsilon^{2}}{2}{\mathsf{opt}} , where {\mathsf{opt}} is the size of the optimal solution. Reference Approximation ratio Query Complexity FastSG (Alg. 2 , this work) \Big((1+\epsilon)(1+\ln(\frac{1}{\delta})),\frac{1-\delta}{2}\Big) O\left(\tfrac{nk\log^{2}(n)}{\epsilon}\log\!\left(\tfrac{n}{\delta}\right)\right) Streaming Algorithm in [ 20 ] \Big(\frac{1-\epsilon}{2\epsilon},\frac{1-\epsilon^{2}}{2}\Big) O(nk\frac{\log(n)}{\epsilon}) Our contribution. In this work, proposed FastSG algorithm for kSC problem with the case f is monotone. FastSG improves the existing bi-criteria approximation to \Big((1+\epsilon)(1+\ln(\frac{1}{\delta})),\frac{1-\delta}{2}\Big) where \epsilon,\delta\in(0,1) is constant parameters in O(nk\log^{3}(n)) . In addition to our theoretical contributions, we conduct extensive experiments comparing our algorithm with the state-of-the-arts. Experimental results on real-world datasets further demonstrate that our approach consistently outperforms them in both running time and solution quality. Table 1 compares our algorithms with the cutting-edge ones for kSC on two aspects including bound of solution quality and query complexity. Additional Related Works. The study of k -submodular optimization was first initiated in the setting of bisubmodular maximization, corresponding to k=2 , by [ 24 ] . Ward et al. [ 30 ] formally investigated the unconstrained k -submodular maximization problem. In their seminal work, they proposed a deterministic greedy algorithm attaining an approximation ratio of 1/3 . Later, [ 9 ] improved this bound to 1/2 for deterministic algorithms and further introduced a randomized greedy variant, achieving an expected ratio of k/(2k-1) by sampling elements according to a probability distribution. Subsequently, [ 18 ] attempted to derandomize the algorithm of [ 9 ] to obtain the same ratio deterministically; however, their method required a large query complexity of O(n^{2}k^{2}) . The k -submodular maximization problem has also been examined under cardinality and other combinatorial constraints. [ 17 ]

Read the complete text