<p>We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classic problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution’s cardinality. If any deleted elements were part of the initial solution, they are replaced with a set of at most equal cardinality. The objective is to maximize the value of the ultimate solution, with the deletion being maximally disadvantageous to the ultimate solution. When the submodular function is <InlineEquation ID="IEq1"> <EquationSource Format="TEX">${{\,\mathrm{ \text {M}^\natural }\,}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mspace width="0.166667em" /> <msup> <mtext>M</mtext> <mo>♮</mo> </msup> <mspace width="0.166667em" /> </mrow> </math></EquationSource> </InlineEquation>-concave, we prove that a simple greedy algorithm computes an optimal solution. When only one element may be deleted, we propose a polynomial running time algorithm with an approximation factor of at least <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\frac{1}{3}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>1</mn> <mn>3</mn> </mfrac> </math></EquationSource> </InlineEquation>. When the number of deletions may become as large as the cardinality parameter, we present a polynomial running time algorithm that approximates an optimal ultimate solution in dependence on the curvature of the submodular function. Furthermore, assuming that the number of allowed deletions is upper bounded by a term of the order of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\frac{k}{\log _2^2(k)}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mi>k</mi> <mrow> <msubsup> <mo>log</mo> <mn>2</mn> <mn>2</mn> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </mfrac> </math></EquationSource> </InlineEquation>, where <i>k</i> is the cardinality parameter, we adapt an algorithm from Bogunovic et al. and show that its approximation factor is at least 0.108.</p>

Recoverable robust cardinality constrained maximization with commitment of a submodular function

期刊论文
出版模式：

开放获取
发表日期：

2026年7月10日

查看全文

Sabine Münch,
Stephen Raach,
Sven de Vries

摘要

We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classic problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution’s cardinality. If any deleted elements were part of the initial solution, they are replaced with a set of at most equal cardinality. The objective is to maximize the value of the ultimate solution, with the deletion being maximally disadvantageous to the ultimate solution. When the submodular function is ${{\,\mathrm{ \text {M}^\natural }\,}}$ $M^{♮}$ -concave, we prove that a simple greedy algorithm computes an optimal solution. When only one element may be deleted, we propose a polynomial running time algorithm with an approximation factor of at least $\frac{1}{3}$ $\frac{1}{3}$ . When the number of deletions may become as large as the cardinality parameter, we present a polynomial running time algorithm that approximates an optimal ultimate solution in dependence on the curvature of the submodular function. Furthermore, assuming that the number of allowed deletions is upper bounded by a term of the order of $\frac{k}{\log _2^2(k)}$ $\frac{k}{{log}_{2}^{2} (k)}$ , where k is the cardinality parameter, we adapt an algorithm from Bogunovic et al. and show that its approximation factor is at least 0.108.