The problem of maximizing k-submodular functions is a classical issue in the field of combinatorial optimization. In our work, we primarily consider an or-submodular function, which is a generalization of k-submodular. For maximizing the or-submodular function problem, we first propose a greedy algorithm to get a <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\frac{1}{r+1}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>1</mn> <mrow> <mi>r</mi> <mo>+</mo> <mn>1</mn> </mrow> </mfrac> </math></EquationSource> </InlineEquation>-approximation ratio under a matroid constraint and design a fast algorithm to reduce its complexity, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$1\le r \le k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>r</mi> <mo>≤</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>. In addition, we also use a greedy algorithm to obtain an approximation solution of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\frac{1}{r+1}(1-e^{-(r+1)})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfrac> <mn>1</mn> <mrow> <mi>r</mi> <mo>+</mo> <mn>1</mn> </mrow> </mfrac> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <msup> <mi>e</mi> <mrow> <mo>-</mo> <mo stretchy="false">(</mo> <mi>r</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for maximizing the or-submodular function with a knapsack constraint, where <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$1\le r \le k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>r</mi> <mo>≤</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>.

The approximation algorithm and fast algorithm for constrained or-submodular maximization problem

期刊论文
发表日期：

2026年5月16日

查看全文

Haifeng Huang,
Qian Liu,
Yang Zhou,
Min Li

摘要

The problem of maximizing k-submodular functions is a classical issue in the field of combinatorial optimization. In our work, we primarily consider an or-submodular function, which is a generalization of k-submodular. For maximizing the or-submodular function problem, we first propose a greedy algorithm to get a $\frac{1}{r+1}$ $\frac{1}{r + 1}$ -approximation ratio under a matroid constraint and design a fast algorithm to reduce its complexity, where $1\le r \le k$ $1 \leq r \leq k$ . In addition, we also use a greedy algorithm to obtain an approximation solution of $\frac{1}{r+1}(1-e^{-(r+1)})$ $\frac{1}{r + 1} (1 - e^{- (r + 1)})$ for maximizing the or-submodular function with a knapsack constraint, where $1\le r \le k$ $1 \leq r \leq k$ .