CS Paper Radar

Greedy+Singleton for knapsack-constrained monotone submodular maximization has approximation ratio exactly $β^\star \approx 0.42944$

Kundan Baliga, Aiden Xie, Aditya Byju

cs.DS cs.DM ·submitted 2026-11-10 04:45 UTC · v1

Abstract

Greedy+Singleton is the textbook heuristic for monotone submodular maximization under a knapsack constraint: it returns the better of the cost-benefit greedy set and the best single item. Its worst-case approximation ratio, known only to lie in $[0.427, 0.42945]$ (Feldman-Nutov-Shoham; Kulik-Schwartz-Shachnai), is exactly an explicit constant $β^\star\approx 0.42944$. In the extremal instances, many cheap "filler" items wear down the value of two large optimal items while greedy spends the budget, until neither fits. This picture gives a sharper factor-revealing relaxation; we bound it analytically near the extremal parameters, up to finitely many interval-arithmetic checks, and certify it elsewhere by an exact branch-and-bound. The matching bad instances are tie-free and checkable by hand. For the version that stops at the first item that does not fit, Wolsey's bound $1-e^{-β_W}\approx 0.35780$, where $e^{β_W}=2-β_W$, is tight; Wolsey stated this for his variant without giving the instances, and we give an explicit family with no ties that also covers comparison with the best feasible singleton. The CELF rule also has ratio exactly $β^\star$.

Comment
26 pages, 4 figures. Code and certificates: https://doi.org/10.5281/zenodo.24023723

Closest papers

Nearest neighbours by meaning across the whole index.

A Combinatorial $(1/2-\varepsilon)$-Approximation for $k$-Submodular Maximization under Multiple Knapsacks

cs.DS ·2026-10-17 ·Siyuan Chen, Suixiang Gao, Zheyu Jiang, Wenguo Yang
similarity 0.69
Abstract · 23 pages

We give a randomized combinatorial \((1/2 - \varepsilon)\)-approximation for nonnegative non-monotone \(k\)-submodular maximization under a fixed number \(d\) of knapsack constraints, for \(k \ge 2 \). The algorithm selects whole elements and follows the proportional top-2 rule of Chen et al. \cite{chen2026}: it samples from the two labels with the largest marginal gains, with probabilities proportional to the positive parts of these gains. Extending their single-knapsack Bellman analysis, we construct a common resource potential and associated resource weights, with potential losses charged to greedy gains. Since these weights depend on the unknown optimum, we discretize their defining coefficients and enumerate monotone guesses over phases determined by resource consumption. This yields an algorithm using at most $\mathcal{A}(d,\varepsilon)(nk+1)^{H+2}$ value queries, where $n$ is the number of elements, $\mathcal{A}(d,\varepsilon)$ depends only on $d$ and $\varepsilon$, and $H=O(d \log(2d) / \varepsilon^2)$. The approximation ratio can be made arbitrarily close to the optimal oracle threshold for \( k=2 \) and is asymptotically tight as \(k \to \infty\).

0.21

Inclusion-wise extremal knapsack problems are (mostly) hard to approximate

cs.DS math.OC ·2026-10-13 ·Fabio Ciccarelli, Fabio Furini, Ulrich Pferschy, Elena Rener
similarity 0.65
Abstract

We study two inclusion-wise extremal variants of the 0-1 Knapsack Problem (KP). Given $n$ items with integer weights and nonnegative costs or profits, the Minimum-Cost Maximal Knapsack Packing Problem seeks a minimum-cost packing for capacity $c$ to which no item can be added, while the Maximum-Profit Minimal Knapsack Cover Problem seeks a maximum-profit cover for threshold $d$ from which no item can be removed. Both problems are weakly $\mathrm{NP}$-hard and pseudo-polynomially solvable, as is the classical KP, but their approximability is fundamentally different: unless $\mathrm{P}=\mathrm{NP}$, with positive values neither problem admits a polynomial-time $2^{p(n)}$-approximation for any polynomial $p$; allowing zero values rules out every multiplicative factor. Even with unit costs for packing and unit profits for covering, neither admits an $n^{1-\varepsilon}$-approximation for any fixed $\varepsilon>0$, whereas a trivial $n$-approximation exists. We identify restrictions that restore approximability. If every item weighs at least a fixed fraction of the capacity, respectively of the threshold, both problems can be solved exactly in polynomial time. For the cover problem, if each weight $w_i$ satisfies $w_i-1\geδ(d-1)$, we give an approximation scheme for arbitrary profits whose running time is polynomial in $n$, $1/\varepsilon$, and $1/δ$. If values equal weights, a fully polynomial-time approximation scheme (FPTAS) was already known for the packing problem; we give an FPTAS for the cover problem, improving on the previously known factor $2$. If value-to-weight ratios differ by at most a factor $κ$, we obtain a $(1+\varepsilon)κ$-approximation for both problems.

0.10

Breaking the 1/3 Barrier for constrained $\boldsymbol{k}$-Submodular Maximization: A Proportional Top-2 Randomized Framework

cs.DS ·2026-09-14 ·Siyuan Chen, Shengminjie Chen, Suixiang Gao, Zheyu Jiang, Chenhao Wang +1 more
similarity 0.61
Abstract

$k$-submodularity generalizes submodularity by allowing each selected element to be assigned one of $k$ labels. We study the maximization of a non-monotone $k$-submodular function, where $k\ge2$, under matroid and knapsack constraints. We develop a proportional top-2 randomized framework that achieves an approximation ratio of $\sqrt2-1\approx0.4142$ under either constraint, breaking the previous $1/3$ barrier. Once an element is selected, its label is chosen from the two labels with the largest marginal gains, with probabilities proportional to their positive parts. The analysis separates replacement, pure-addition, and residual-deletion losses, and proves a sharp local loss certificate for this rule. We then give a Bellman analysis using the same local certificate. It gives a $1/2$-approximation under a cardinality constraint and strengthens the knapsack guarantee to $1/2$ without changing the algorithm. The $1/2$ guarantees are oracle-optimal for $k=2$ and asymptotically tight as $k\to\infty$. The value-oracle complexities are $O(Bnk)$ for cardinality, where $B$ is the cardinality bound, $O(n^2k)$ for matroid, and $O(n^3k^2)$ for knapsack.

0.20

Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse

cs.DS cs.LG ·2026-11-15 ·Vaneet Aggarwal
theory similarity 0.61
Abstract

We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every $ε>0$, we give an algorithm with recourse $O(ε^{-2})$ whose reported set has, at every time, expected value at least $1/4-ε$ times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above $1/4$, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above $1/4$ requires recourse that grows as a positive power of the cardinality budget. Thus $1/4$ is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was $3-2\sqrt2\approx0.172$. Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.

0.12

A Sharp Barrier of Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

cs.DS cs.LG ·2026-09-09 ·Shi Fu, Qixin Zhang, Dacheng Tao
theory similarity 0.60
Abstract

Consistent submodular maximization aims to maintain a high-utility subset of size at most $k$ as new elements arrive one by one, while changing only a limited number of elements per update. Previously, [DFL+25](STOC '25) established an information-theoretic bound of $2/3$ and gave the first polynomial-time randomized algorithm with a $0.51$-approximation guarantee. However, a fundamental question remained open: Is it possible to design an efficient algorithm for consistent submodular maximization that matches the classical offline $(1-1/e)$-approximation? In this paper, we answer this question in the negative by proving that the sharp approximation threshold achievable with polynomially many value queries and worst-case constant recourse is \[β:=2-\sqrt{2}\approx0.5858<1-1/e.\] Specifically, we develop an improved poly-time randomized algorithm, which can attain a $(β-\varepsilon)$-approximation in expectation at each fixed time with $O(\varepsilon^{-2})$ worst-case recourse. The cornerstone of this algorithm is a novel anchored sampling scheme, which uses only value queries on subsets of the elements seen so far to construct a solution that remains competitive under unknown future arrivals. Conversely, we establish a matching lower bound by showing that any fixed improvement over $β$ requires either exponentially many value queries or $Ω(k)$ changes per update. Furthermore, we characterize the impact of curvature by establishing a sharp threshold of $1-(\sqrt{2}-1)\vartheta$ for consistent submodular maximization, where $\vartheta\in[0,1]$ denotes the total curvature. Surprisingly, for weighted coverage objectives, we devise a poly-time randomized algorithm that can match the optimal $(1-1/e-\varepsilon)$-approximation with $O(\varepsilon^{-1})$ worst-case recourse, thereby separating coverage maximization from general submodular maximization in the consistent settings.

0.45

Online Submodular Welfare Maximization: Computation is not the Bottleneck

cs.DS math.OC ·2026-10-12 ·Rajan Udwani, David Wajc
publishedhighly cited similarity 0.59
Abstract · In FOCS 2026

We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite matching, display ads and AdWords. A natural greedy OSW algorithm achieves a competitive ratio of $1/2$ [LLN06], and $1-1/e$ under i.i.d. arrivals [KPV13]. Both bounds are tight for polynomial-time algorithms unless NP=RP [KPV13]. The information-theoretic limits for OSW, in contrast, remained open. This prompted researchers to ask for tighter upper bounds [Mehta13] or conjecture the existence of better-competitive (slow) algorithms [Huang23, LTX+23, CHS24, Huang2024, HTW24}. We resolve Mehta's question and refute the subsequent conjectures, proving that the greedy algorithm is in fact tight for both adversarial and i.i.d. arrivals, regardless of computation time. Seemingly contradicting recent $(1-1/e)$-competitive fractional algorithms for OSW [HJP+24,Patton26], we show that this impossibility even holds for fractional algorithms, provided their outputs correspond to marginals that are roundable in hindsight. Conceptually, our proofs can be seen as identifying that a bottleneck for OSW, even under (deterministic) adversarial arrivals, is the inherently random notion of correlation gap [ADSY12].

0.55

Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint

cs.DS ·2026-09-22 ·Zihui Liu, Zhijie Zhang
similarity 0.59
Abstract · ISAAC 2026

Submodular maximization under a knapsack constraint (SMK) is a fundamental combinatorial optimization problem with broad applications across machine learning and data mining. Motivated by large-scale applications where query efficiency is paramount, we study non-monotone SMK and focus on deterministic algorithms with linear query complexity. Prior deterministic linear-query algorithms achieve at best a $1/5-\varepsilon$ approximation, falling short of the $1/4-\varepsilon$ ratio attainable by randomized algorithms. We close this gap by presenting a deterministic $(1/4-\varepsilon)$-approximation with $O(n\log^2(1/\varepsilon)/\varepsilon^2)$ queries. Our approach partitions the analysis based on the cost of the largest optimal element $r$: when the cost of $r$ is moderate, we refine the threshold-twin-greedy framework via residual-budget enumeration to tighten the analysis; when the cost of $r$ is large, we reduce the problem to bicriteria submodular maximization. As a secondary contribution, we obtain a $(1/2-\varepsilon, O(1/\varepsilon))$-bicriteria approximation with $O(n\log(1/\varepsilon)/\varepsilon^2)$ queries, improving over the previous $O(n^2/\varepsilon)$ query bound.

0.37

Single-Sample Prophet Inequalities: A Combinatorial to Single-Item Reduction

cs.GT cs.DS ·2026-10-02 ·Shuchi Chawla, Trung Dang
similarity 0.58
Abstract

We study single-sample prophet inequalities for online combinatorial allocation. Our main contribution is a general reduction from combinatorial to single-item prophet inequalities for valuation classes admitting suitable supporting prices. The reduction uses a free-disposal value to separate buyer-side combinatorial constraints from item-side supply constraints, yielding a modular framework that applies in the stronger Game of Googol model. This framework yields a $\frac{1}{6\sqrt{3}}\approx\frac{1}{10.4}$-competitive single-sample prophet inequality and a $(β_{k-1}/4)$-competitive $k$-sample prophet inequality for XOS valuations, where $β_k$ is the competitive ratio of a $k$-sample single-item prophet inequality, improving upon the work of [DKL+24]. Both results extend directly to divisible resources with capped-XOS valuations. Along the way, we obtain new results for online free disposal and an optimal single-sample prophet inequality for fractional knapsack in the Game of Googol model.

0.30