Submodular optimization problems have received increasing attention in recent years. And the k-submodular function as a generalization of the submodular function is also getting more and more attention. The k-submodular optimization problems have important applications in influence maximization problems and sensor placement problems with k kinds of sensors. In this paper, we study the problems of maximizing k-submodular functions subject to two kinds of constraints. For the p-system constraint, we get a <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\frac{1}{p+1}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>1</mn> <mrow> <mi>p</mi> <mo>+</mo> <mn>1</mn> </mrow> </mfrac> </math></EquationSource> </InlineEquation>-approximation ratio when f is monotone and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\frac{1}{p+2}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>1</mn> <mrow> <mi>p</mi> <mo>+</mo> <mn>2</mn> </mrow> </mfrac> </math></EquationSource> </InlineEquation>-approximation ratio when f is non-monotone. For the intersection of p-system and d-knapsack constraints, we set <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\alpha =2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> when f is monotone and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\alpha =3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> when f is non-monotone. Then we get an approximation ratio of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\frac{1-\epsilon }{p+\alpha +2d}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mrow> <mn>1</mn> <mo>-</mo> <mi>ϵ</mi> </mrow> <mrow> <mi>p</mi> <mo>+</mo> <mi>α</mi> <mo>+</mo> <mn>2</mn> <mi>d</mi> </mrow> </mfrac> </math></EquationSource> </InlineEquation>. And subsequently, we propose an improved algorithm that improves the approximation ratio to <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\frac{1-\epsilon }{p+\alpha +\frac{7}{4}d}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mrow> <mn>1</mn> <mo>-</mo> <mi>ϵ</mi> </mrow> <mrow> <mi>p</mi> <mo>+</mo> <mi>α</mi> <mo>+</mo> <mfrac> <mn>7</mn> <mn>4</mn> </mfrac> <mi>d</mi> </mrow> </mfrac> </math></EquationSource> </InlineEquation>.

On maximizing k-submodular functions under p-system and d-knapsack constraints

期刊论文
发表日期：

2026年2月9日

查看全文

Wenzhe Zhang,
Shufang Gong,
Bin Liu,
Qian Liu,
Priyanshi Garg

摘要

Submodular optimization problems have received increasing attention in recent years. And the k-submodular function as a generalization of the submodular function is also getting more and more attention. The k-submodular optimization problems have important applications in influence maximization problems and sensor placement problems with k kinds of sensors. In this paper, we study the problems of maximizing k-submodular functions subject to two kinds of constraints. For the p-system constraint, we get a $\frac{1}{p+1}$ $\frac{1}{p + 1}$ -approximation ratio when f is monotone and $\frac{1}{p+2}$ $\frac{1}{p + 2}$ -approximation ratio when f is non-monotone. For the intersection of p-system and d-knapsack constraints, we set $\alpha =2$ $α = 2$ when f is monotone and $\alpha =3$ $α = 3$ when f is non-monotone. Then we get an approximation ratio of $\frac{1-\epsilon }{p+\alpha +2d}$ $\frac{1 - ϵ}{p + α + 2 d}$ . And subsequently, we propose an improved algorithm that improves the approximation ratio to $\frac{1-\epsilon }{p+\alpha +\frac{7}{4}d}$ $\frac{1 - ϵ}{p + α + \frac{7}{4} d}$ .