CS Paper Radar

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

Fabio Ciccarelli, Fabio Furini, Ulrich Pferschy, Elena Rener

cs.DS math.OC ·submitted 2026-10-13 09:14 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

A PTAS for Non-Adaptive Stochastic Top-$k$ Sum under General Combinatorial Constraints

cs.DS cs.CC ·2026-09-03 ·Yu Liu
similarity 0.69
Abstract · Expanded the topk minimization problem with covering dual, as my thesis paper did

We study non-adaptive selection of a feasible set $S$ that maximizes the expected sum of the $k$ largest realized values among independent nonnegative discrete random variables. The same objective arises in team hiring and as VCG welfare in an $\ell$-unit auction. The main setting is a fixed-dimensional nonnegative packing family, whose natural LP has $d=O(1)$ packing inequalities with binary coefficients. We give a PTAS for every $k\ge 1$ on every such family, including binary one- and two-dimensional knapsack, by approximating the occupancy functional $p\mapsto\mathbb{E}[\min(k,N(p))]$ and realizing the resulting signatures in the packing LP. As a generic guarantee the scheme is essentially optimal: there is no FPTAS that works for every such $\mathcal{F}$ unless $P=NP$, and no EPTAS unless $W[1]=FPT$. An incomparable sufficient condition is a query-weight exact-sum oracle (DAG paths, matchings), which likewise yields a PTAS for every $k$. The same signatures give a PTAS for $\min_{S\in\mathcal{F}}\mathbb{E}[\mathrm{Top}_k(S)]$ on every fixed-$d$ covering family; two-dimensional covering knapsack rules out a generic FPTAS on that class.

0.31

Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Bicriteria Optimality in 2D

cs.DS ·2026-08-27 ·Karl Bringmann, Ariel Kulik, Karol Węgrzycki
theory similarity 0.67
Abstract · Abstract shortened to fit ArXiV requirements

We revisit the $d$-dimensional Vector Knapsack problem ($d$-Knapsack): Given a $d$-dimensional capacity vector and a set of items, each with a $d$-dimensional weight vector and a profit, the goal is to select a set of items that maximizes the total profit without exceeding the capacity in any dimension. For any $d\ge2$, the best known approximation scheme for $d$-Knapsack runs in time $O(n^{\lceil d/\varepsilon\rceil-d})$ [Caprara, Kellerer, Pferschy, Pisinger '00]. We improve this running time to $\widetilde O_{d,\varepsilon,ρ}(n^{\lceil\frac{d-1}{2\varepsilon}-\frac12+ρ\rceil}+n^d)$ for any $\varepsilon\in(0,1)$ and every parameter $ρ\in(0,1)$. We achieve this speedup by designing the first meet-in-the-middle algorithm for $d$-Knapsack. This requires replacing the LP solver used in prior algorithms by a highly efficient dynamic programming algorithm to generate representative solutions, building on an LP-based structural argument. This is the first improvement in over 25 years, and the first result that improves the exponent by a constant factor. We complement this by a fine-grained lower bound based on $k$-SUM showing that 2-Knapsack requires time $n^{\lceil\frac1{2\varepsilon}-\frac12 \rceil-o(1)}$. This establishes the optimal exponent of 2-Knapsack as $\frac1{2\varepsilon}\pm O(1)$, which is precise up to an additive $O(1)$. To the best of our knowledge, this is the first result that determines the optimal exponent more precisely than up to a factor $O(1)$, for any problem that admits a PTAS but no EPTAS. For the special case of 2-Knapsack we further attain a $(1-\varepsilon-δ)$-approximation in time $\widetilde O_{δ,\varepsilon}(n^{\lceil\frac1{2\varepsilon}-\frac12\rceil})$. This nearly matches our lower bound, as for a slightly better approximation ratio a slightly better running time is impossible -- so our algorithm is bicriteria-optimal.

0.25

A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem

cs.DS math.OC ·2026-09-15 ·Fabio Ciccarelli, Fabio Furini
similarity 0.66
Abstract

The $\textit{Colored Knapsack Problem}$ (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an ordering in which consecutive items have different colors. The problem is weakly $\mathcal{NP}$-hard and admits two pseudo-polynomial dynamic programming (DP) algorithms proposed in the literature. These two DP algorithms have worst-case running times $O(b \, n^4)$ and $O(b^2 \, n^3)$, respectively, where $b$ is the knapsack capacity and $n$ is the number of items. We develop the first approximation algorithm for the ColKP. By rounding an optimal basic solution of the linear programming relaxation of its natural integer programming formulation and repairing color feasibility, we obtain a linear-time approximation-algorithm whose worst-case performance ratio is $1/3$. We then reformulate both DP algorithms so that profit, rather than knapsack capacity, indexes their pseudo-polynomial dimension, and combine them with profit scaling to obtain two fully polynomial-time approximation schemes (FPTASs). The first FPTAS runs in $O(n^5/\varepsilon)$ time for nonnegative profits and in $O(n^6/\varepsilon)$ time for arbitrary integer profits. The second FPTAS runs instead in $O(n^5/\varepsilon^2)$ and $O(n^7/\varepsilon^2)$ time, respectively. The approximation guarantee, along with new structural insights, provides the bounds needed to control the scaled profit range and establish these running times.

0.27

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

cs.DS cs.DM ·2026-11-10 ·Kundan Baliga, Aiden Xie, Aditya Byju
similarity 0.65
Abstract · 26 pages, 4 figures. Code and certificates: https://doi.org/10.5281/zenodo.24023723

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$.

0.30

Faster Deterministic Approximation for Counting Knapsack

cs.DS ·2026-10-10 ·Ce Jin, Jaewoo Park, Barna Saha
top venue similarity 0.65
Abstract · To appear in SODA 2027. 32 pages

Given $n$ nonnegative integer weights $w_1, \ldots, w_n$ and an integer knapsack capacity $T$, the $\#$Knapsack problem asks to count the number of subsets $I \subseteq \{1, 2, \dots, n\}$ such that $\sum_{i \in I} w_i \le T$. A long line of research has been devoted to designing faster $(1 \pm \varepsilon)$-approximation algorithms for this \#P-hard problem. Until very recently, the best-known time complexity was $\tilde{O}\bigl(n^{2.5}/\mathrm{poly}(\varepsilon)\bigr)$, achieved by the randomized algorithm of [Dyer, STOC 2003] and the deterministic algorithm of [Gawrychowski, Markin, and Weimann, ICALP 2018]. The recent work by [Feng and Jin, SODA 2025] improved the randomized complexity to $\tilde{O}\bigl(n^{1.5}/\mathrm{poly}(\varepsilon)\bigr)$, leaving open the question whether this $n^{2.5}$ barrier could also be broken by a \emph{deterministic} algorithm. In this work, we answer this question in the affirmative by presenting a deterministic $(1 + \varepsilon)$-approximation algorithm for \#Knapsack in $\tilde{O}\bigl(n^{2.4}/\mathrm{poly}(\varepsilon)\bigr)$ time. Our key technical innovation is to deterministically simulate the balancing technique, which was previously used in the literature of knapsack-type problems via random partitions and seemed to require randomization.

0.51

Additive $Ω(\log^* OPT)$ Gap for Bin Packing with Three Items per Bin

cs.DS ·2026-11-06 ·Ilan Doron-Arad
theory similarity 0.63
Abstract

We prove that bin packing is NP-hard to approximate within an additive factor of $o(\ls\OPT)$, even when all item sizes are arbitrarily close to $1/3$. This gives the first lower bound for bin packing with an additive factor that depends explicitly on the optimum value. In addition, we give a polynomial-time reduction from any bin packing instance into one with item sizes arbitrarily close to $1/3$, preserving its additive configuration-LP gap up to constant factors. Thus, in the sense of additive configuration LP gap and up to a constant, we confirm the conjecture that 3-partition instances are the hardest bin packing instances. In particular, we obtain an unconditional $Ω(\ls\OPT)$ gap for 3-partition instances. We build on the recent OpenAI construction that uses five items per bin and rules out any constant additive gap.

0.25

Fair and Efficient Allocations: Decision Problems in the Gap of Polynomial Hierarchy

cs.GT ·2026-09-25 ·Xiaolin Bu, Biaoshuai Tao
published similarity 0.62
Abstract · Accepted by WINE'26

We consider the fair division problem with indivisible goods and study the following decision problem: given a fair division instance, does there exist an allocation that is envy-free and efficient? We consider two efficiency criteria: Pareto-optimality and social welfare optimality. We provide a complete landscape on the computational complexity of this decision problem, with the number of agents ranging from $2$ to $\infty$, both additive valuations and general valuations, and the more restricted class of $k$-ary valuation functions (where an item's marginal value is restricted to $\{0,1,\ldots,k-1\}$ for some constant $k\geq2$). One interesting observation is that many versions of the above-mentioned decision problems fall into the ``gap'' between the first and the second levels of the polynomial hierarchy. Specifically, assuming the polynomial hierarchy does not collapse to the first level (i.e., assuming $\text{NP}\neq\text{coNP}$), these problems are in $(Σ_2^{\text{p}}\capΠ_2^{\text{p}})\setminus(\text{NP}\cup\text{coNP})$. In particular, we provide a fine-grained complexity analysis across different parameter regimes, including the number of agents and the choice of valuation models. Depending on different parameters, many problems admit different complexity classifications, ranging from the intermediate classes $Θ_2^{\text{p}}$ and $Δ_2^{\text{p}}$ between the two levels to $Σ_2^{\text{p}}$-completeness. Finally, De Keijzer et al. show the $Σ_2^{\text{p}}$-completeness of the decision problem when considering Pareto-optimality as the efficiency criterion with additive valuations. Our main results extend this result to more restricted settings, such as instances with a constant number of agents or $3$-ary valuation functions, which resolves the open problem given by Bouveret and Lang.

0.16

Tight Approximation Results for Matroid Optimization with a Linear Constraint

cs.DS ·2026-09-23 ·Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler
similarity 0.62
Abstract

We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions $v,w:E\to R_{\ge 0}$, and a threshold $L\in R_{\ge 0}$, find $opt v(S)$ where S is either an independent set or a base of M satisfying a budget-type constraint: $w(S)\le L$ or $w(S)\ge L$, and $opt\in\{min,max\}$. P-MOL provides a unified representation for a broad family of NP-hard optimization problems, including budgeted matroid independent set, constrained minimum-basis, and knapsack-cover variants with a matroid constraint. Also, it naturally extends to multiple matroid constraints. In particular, we consider the matroid intersection cover (MIC) problem, where feasibility is defined by the common independent sets of two matroids and one seeks minimum $v(S)$ subject to $w(S)\ge L$. Our main result is a unified EPTAS for all nontrivial P-MOL variants, obtained by generalizing a technique of Hassin and Levin (SIAM J. Comput., 2004) for solving the constrained minimum spanning tree problem. Specifically, for any fixed $ε>0$, we present an algorithm running in time $|E|^{O(1)} (1/{ε^2})^{O(1/ε)}$ that outputs a feasible solution S whose value is at most $(1+ε)OPT$ for minimization variants and at least $(1-ε)OPT$ for maximization variants. This resolves the complexity status of all members of P-MOL, as none of these problems admits an FPTAS (Doron-Arad, Kulik and Shachnai, ICALP'24). Finally, we separate the P-MOL family from its extension to matroid intersection. We show that an EPTAS is unlikely to exist for the matroid intersection variant of P-MOL under a covering constraint, whereas an EPTAS is known to exist under a budget constraint. This highlights a qualitative difference between these two types of linear constraints that does not arise in the single-matroid setting.

0.14