CS Paper Radar

Grid Theory and Polynomiality in Dynamic Lot-Sizing

El-Mehdi Mehiri, Nabil Absi, Elodie Suzanne

cs.DM math.OCcs.DSmath.CO ·submitted 2026-10-02 16:39 UTC · v1
theory

Abstract

Why are some dynamic lot-sizing problems polynomial? We address this question by introducing Grid Theory, a structural framework based on cumulative production and the additive structure of production bounds. For a general single-item dynamic lot-sizing model with lower and upper production bounds, there exists an optimal extreme solution in which, within each regeneration interval, all but at most one production quantity lie on a boundary value. This induces additive grids, and the Main Grid Theorem establishes that an optimal cumulative production trajectory can be restricted to these discrete sets. Although the resulting grids may be exponentially large, we introduce the notion of additive dimension to capture production-bound profiles whose boundary sums admit a low-dimensional representation. We show that bounded additive dimension yields a polynomially constructible grid envelope and a polynomial time grid-based dynamic programming algorithm. The framework extends to separable concave costs and establishes polynomial solvability of several families, including constant capacities, minimum order quantities, a fixed number of capacity levels, fixed-degree polynomial capacities, periodic capacities, and piecewise polynomial capacities. In particular, polynomiality may hold even when the number of distinct capacity values grows with the planning horizon. Grid Theory thus identifies additive structure, rather than the number of distinct resource values, as a sufficient mechanism for polynomial solvability.

Closest papers

Nearest neighbours by meaning across the whole index.

Critical-state algorithms for lot sizing with all-units discounts and variable inventory bounds

cs.DS ·2026-10-16 ·Kleitos Papadopoulos
theory similarity 0.65
Abstract

We study deterministic single-item lot sizing with all-units quantity discounts, linear holding costs, and time-varying end-of-period inventory bounds. Unit prices may vary arbitrarily over time. For one common positive discount threshold, we give an exact algorithm requiring $O(n^3)$ arithmetic operations and $O(n^2)$ working space, including recovery of an optimal purchase plan. The method combines a critical-state theorem in cumulative-purchase coordinates with two prefix-minimum scans per dynamic-programming layer. The structural argument accommodates downward price discontinuities and distinguishes prescribed from free terminal inventory. With a fixed global set of $m$ positive threshold values, the bounds become $O_m(n^{m+2})$ time and $O_m(n^{m+1})$ space. Period-specific thresholds admit the same exact construction, but its state set can be exponential. For commensurate flow data, an inventory-lattice implementation takes $O(PW)$ time, where $P$ is the total number of price tiers and $W$ is the largest inventory-lattice width. We also derive a conditional optimality certificate from a monotone one-threshold relaxation; this certificate does not imply a near-linear worst-case algorithm for arbitrary prices. Exact-arithmetic implementations are checked against exhaustive inventory dynamic programs and tier-enumeration linear programs. An illustrative timing study identifies settings in which the lattice implementation is preferable.

0.23

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

High-Multiplicity Bin Packing is FPT

cs.DS ·2026-09-15 ·Tomohiro Koana, Soh Kumabe
similarity 0.55
Abstract

Bin packing asks whether a collection of items can be packed into at most a given number of bins of a given capacity. We consider the high-multiplicity setting with $d$ distinct item sizes, in which both the item sizes and the number of items of each size are encoded in binary. Goemans and Rothvos (JACM 2020) gave an XP algorithm parameterized by $d$. Whether this problem is fixed-parameter tractable (FPT) in $d$ has remained a central open problem. We resolve this question by giving a deterministic $O^*(2^{d^{O(d)}})$-time algorithm. We formulate bin packing as an integer linear program (ILP) with at most $(d+1)d^d$ variables. A bin configuration records the number of items of each type in one bin. We partition these configurations by their coordinate remainders modulo $d$. For each class, we use one variable for the bin count and $d$ variables for the total item counts. The convex hull of each class has the integer decomposition property, which guarantees that every feasible ILP solution corresponds to a packing.

0.57

The Complexity of Continuous Contract Design over Polymatroids

cs.GT ·2026-11-03 ·Max Klimm, Paul Lippke, Philipp Warode
theorycode/data similarity 0.55
Abstract · 89 pages, 6 figures. The Lean 4 formalization is at https://github.com/philippwarode/contract-design-polymatroids-lean

We study optimal contracts when an agent allocates continuous effort subject to polymatroid capacity constraints. Effort produces a linear expected reward and incurs a cost. With binary outcomes and limited liability, the principal chooses a single reward share. For linear costs, an optimal contract can be computed in polynomial time. For quadratic costs, the agent has a unique best response computable by polynomially many submodular minimizations, yet optimizing the principal's share is NP-hard even for explicitly represented cut-based rank functions. With $n$ activities, the best-response path can have $2^{n-O(\log n)}$ breakpoints even when each reward coefficient and each rank value is an integer representable in $O(n\log n)$ bits. The construction also answers a question of Allman, Lo, and McCormick on polynomial bit length for source-sink monotone two-parameter minimum cuts. Despite this complexity, an optimal contract for quadratic costs always exists with a share of at most $1/2$. Consequently, $O(1/\varepsilon)$ best-response computations suffice for a $(1-\varepsilon)$-approximation. For rational quadratic costs on explicitly described rational polytopes containing zero, this gives a fully polynomial-time approximation scheme. More generally, a share of at most $1/p$ suffices for continuous convex costs homogeneous of degree $p>1$, on any compact convex action set containing zero. For general convex costs with an exact value and bounded-subgradient oracle, we obtain an oracle approximation scheme using approximate best responses and a supplied lower bound on positive welfare.

0.43

Computing Equilibria in Integer Programming Games with Shared Constraints

cs.GT math.OC ·2026-10-03 ·Bainian Hao, Hyunwoo Lee, Robert Hildebrand, Carla Michini
similarity 0.55
Abstract

We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent profile and infeasible against another. Conditional equilibrium inequalities capture this dependence through an explicit activation term. We give affine encodings of costs and activation conditions and prove that the resulting inequalities characterize the equilibrium set exactly. Embedded as lazy constraints in branch-and-cut, they yield the Generalized Zero-Regret algorithm for optimizing a linear objective over exact or approximate equilibria; a bisection procedure maintains certified bounds on the smallest achievable approximation factor. We also prove that, when the conditional polytopes have integral vertices, a concave cost is constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies; for uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity. We give formulations for bin packing, network formation, and knapsack games with shared capacities and evaluate the algorithm on 3,300 instances, computing a socially optimal equilibrium on all but 43, certifying nonexistence on 16, and certifying approximation factors within a few percent where no exact equilibrium exists.

0.41

Entropic Column Generation and Lehmer Branch-and-Price for Bin Packing Problem

cs.DM math.OC ·2026-10-31 ·Masoud Ataei
benchmarkcode/data similarity 0.55
Abstract · 38 pages, 1 figure, 8 tables. Code: https://github.com/chimera1001/lehmer-bp

We introduce Lehmer branch-and-price, an exact algorithm for bin packing and cutting stock problems built on the Lehmer transform, the ratio of Mellin transforms of item weights at consecutive orders. The transform maps each bin, a finite multiset of item weights, to a smooth increasing curve, and so gives the discrete problem a continuous representation on which the tools of analysis, such as convexity, exponential families and smoothing, can act. Read along this curve, the problem yields an explicit dual solution, a monotone representation of the dominance order, a family of constructive heuristics with first fit decreasing as its limit, and an integer identity that tells when the linear relaxation can decide an instance and when only a perfect packing can improve the best solution known. Lifted from items to patterns, the transform gives entropic column generation, a new form of column generation that bounds the relaxation from both sides at every iteration without solving the pricing problem exactly, maximizes a smoothed dual at an explicit rate, and measures by an entropy how much the relaxation leaves undecided. We show that the proposed algorithm outperforms the state-of-the-art methods on the standard benchmark in both the number of instances solved and the computational time.

0.40

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

cs.GT ·2026-09-25 ·Xiaolin Bu, Biaoshuai Tao
published similarity 0.54
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

Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date

cs.CC math.OCcs.DMmath.CO ·2026-09-12 ·Nicholas G. Hall, Hans Kellerer, Miao Song
similarity 0.54
Abstract · 268 pages, 12 figures, 29 tables

Single-machine asymmetric weighted earliness--tardiness (AWET) scheduling asks how to sequence jobs around a common synchronization date when early and late completion incur unrelated job-dependent penalties. At the boundary nonrestrictive date $d=\sum_jp_j$, a compact V-shaped schedule reduces the continuous-time problem to a quadratic choice of a nonempty early set. We establish four complementary results for this model. First, the positive-integer problem is strongly NP-complete by a unary-polynomial reduction from Restricted Exact Cover by 3-Sets. Second, unrestricted AWET admits a polynomial-time $(3+2\sqrt2+\varepsilon)$-approximation based on an anchored semidefinite relaxation and deterministic marginal thresholding. Third, when the earliness and tardiness ratio orders are strict reversals, the problem is weakly NP-complete but has an exact two-resource pseudopolynomial dynamic program. Fourth, for fixed total refinements whose ratio permutation is separable, an exact separating-tree recurrence and coordinated geometric trimming yield an FPTAS. The proofs use different manifestations of the same canonical objective: scale-separated prefix penalties, positive-semidefinite minimum-kernel covariance, a dominant completed load square, and a bounded four-coordinate decomposition interface. Together, the results show that the decisive issue is not merely whether the two ratio orders agree, but whether their interaction can be controlled by a global certificate or compressed into a bounded constructive interface.

0.21