As a generalization of submodular functions, k-submodular functions have broad applications in machine learning, including multi-type sensor placement, multi-topic influence maximization, and coupled feature selection, etc. Many optimization problems in the real world often involve uncertainty, and the risk of violating constraints caused by these random factors needs to be strictly controlled. In this paper, we study the k-submodular maximization problem with the chance constraint and propose two algorithms with linear query complexity. The first algorithm achieves an approximation ratio close to 1/4 for monotone f, and close to 1/5 for non-monotone f, using a query complexity <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(\frac{nk}{\epsilon })$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mfrac> <mrow> <mi mathvariant="italic">nk</mi> </mrow> <mi>ϵ</mi> </mfrac> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Furthermore, the second algorithm achieves an approximation ratio close to 1/3 for monotone f, and close to 1/4 for non-monotone f, using a query complexity <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(\frac{nk}{\epsilon }\log \frac{1}{\epsilon })$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mfrac> <mrow> <mi mathvariant="italic">nk</mi> </mrow> <mi>ϵ</mi> </mfrac> <mo>log</mo> <mfrac> <mn>1</mn> <mi>ϵ</mi> </mfrac> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\epsilon \in (0,1/5)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϵ</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>5</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is a small constant.

Deterministic algorithms for k-submodular maximization with the chance constraint

期刊论文
发表日期：

2026年7月25日

查看全文

Shufang Gong,
Qiao Chen,
Bin Liu

摘要

As a generalization of submodular functions, k-submodular functions have broad applications in machine learning, including multi-type sensor placement, multi-topic influence maximization, and coupled feature selection, etc. Many optimization problems in the real world often involve uncertainty, and the risk of violating constraints caused by these random factors needs to be strictly controlled. In this paper, we study the k-submodular maximization problem with the chance constraint and propose two algorithms with linear query complexity. The first algorithm achieves an approximation ratio close to 1/4 for monotone f, and close to 1/5 for non-monotone f, using a query complexity $O(\frac{nk}{\epsilon })$ $O (\frac{nk}{ϵ})$ . Furthermore, the second algorithm achieves an approximation ratio close to 1/3 for monotone f, and close to 1/4 for non-monotone f, using a query complexity $O(\frac{nk}{\epsilon }\log \frac{1}{\epsilon })$ $O (\frac{nk}{ϵ} log \frac{1}{ϵ})$ , where $\epsilon \in (0,1/5)$ $ϵ \in (0, 1 / 5)$ is a small constant.