<p>Submodularity captures the property of diminishing marginal returns and is essential in combinatorial optimization and machine learning, where many problems can be formulated as the maximization of a submodular function under specific constraints. One widely studied constraint is the knapsack constraint, which models the fact that elements have distinct capacity requirements. In this paper, we propose a new capacity constraint, referred to as the Pairwise Capacity Constraint, which can be viewed as a special case of the multi-knapsack constraint. For the monotone submodular maximization problem subject to this constraint, we propose a <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\frac{1}{4}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>1</mn> <mn>4</mn> </mfrac> </math></EquationSource> </InlineEquation>-approximation greedy algorithm. By establishing a connection to a matroid constrained problem, we further develop an optimal <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$(1-\frac{1}{\textrm{e}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <mfrac> <mn>1</mn> <mtext>e</mtext> </mfrac> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximation offline algorithm. Additionally, we present a <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\frac{1}{4}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>1</mn> <mn>4</mn> </mfrac> </math></EquationSource> </InlineEquation>-approximation streaming algorithm based on concave closure relaxation and the primal-dual method. This streaming algorithm queries the value oracle of the objective function only once per element and has a memory complexity of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(k\log k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo>log</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <i>k</i> is defined as the maximum cardinality among all solutions that satisfy the Pairwise Capacity Constraint.</p>

Monotone submodular maximization under the pairwise capacity constraint

期刊论文
发表日期：

2025年12月15日

查看全文

Yuanyuan Qiang,
Bin Liu,
Weili Wu

摘要

Submodularity captures the property of diminishing marginal returns and is essential in combinatorial optimization and machine learning, where many problems can be formulated as the maximization of a submodular function under specific constraints. One widely studied constraint is the knapsack constraint, which models the fact that elements have distinct capacity requirements. In this paper, we propose a new capacity constraint, referred to as the Pairwise Capacity Constraint, which can be viewed as a special case of the multi-knapsack constraint. For the monotone submodular maximization problem subject to this constraint, we propose a $\frac{1}{4}$ $\frac{1}{4}$ -approximation greedy algorithm. By establishing a connection to a matroid constrained problem, we further develop an optimal $(1-\frac{1}{\textrm{e}})$ $(1 - \frac{1}{e})$ -approximation offline algorithm. Additionally, we present a $\frac{1}{4}$ $\frac{1}{4}$ -approximation streaming algorithm based on concave closure relaxation and the primal-dual method. This streaming algorithm queries the value oracle of the objective function only once per element and has a memory complexity of $O(k\log k)$ $O (k log k)$ , where k is defined as the maximum cardinality among all solutions that satisfy the Pairwise Capacity Constraint.